Złożoność obliczeniowa/Wykład 5: Problemy NP-zupełne

Wstęp

Jak czytelnikowi wiadomo, w aktualnym stanie wiedzy NP-zupełność jest podstawowym narzędziem do badania probelu algorytmicznego pod kątem jego trudności obliczeniowej. Na tym wykładzie dla wielu znanych klasycznych problemów z teorii grafów, kombinatoryki, logiki i innych podajemy definicje ich decyzyjnych wersji i wykazujemy ich NP-zupełność. Z problematyką tą spotkaliśmy się już na kursie Algorytmy i struktury danych. Tutaj rozbudowujemy te wiadomości, czynimy je bardziej formalnymi, posługując się modelem maszyny Turinga i redukcją logarytmiczną. Na przedstawionych przykładach omawiamy również techniki dowodzenia NP-zupełności. Następny wykład pokazuje wykorzystanie tych technik do analizy złożoności problemu i jego zawężeń.

O problemie SAT

Aby wykazać, że dany problem $Q$ z klasy NP jest NP-zupełny, zgodnie z własnościami redukcji logarytmicznej (przechodniość) wystarcza pokazać, dla dowolnego problemu $Q^{\prime }\in NPC$, że $Q^{\prime }$ redukuje się do $Q$. Innymi słowy, proces dowodzenia że dany problem $Q$ jest w NPC składa sie z nastepujących kroków:

• dowieść że $Q$ należy do NP

• wybrać znany problem NP-zupełny $Q^{\prime }$ i skonstruować redukcję z $Q^{\prime }$ do $Q$.

Przypomnijemy, że redukcja z problemu A do B dowodzi, że B jest niełatwiejszy niż A. Zatem dla konstrukcji takiej redukcji łatwiej jest, gdy (są to rozważania czysto intuicyjne):

• problem A nie jest skomplikowany, tzn. instancje tego problemu wykazują pewną regularność, łatwą do "opisu" lub "zmierzenia"

• problem B dopuszcza konstrukcje różnorodnych instancji, jest "bogaty strukturalnie"

Stąd dla wypracowania sobie "warsztatu" dla konstruowania dowodów NP-zupełności warto rozpocząć od dowiedzenia tej własności dla kilku nieskomplikowanych (pod wzgledem opisu struktury) problemów. W rzeczywistości, w literaturze dotyczącej tych zagadnień, można wyodrębnić niewielką grupę klasycznych w tym sensie problemów, które najczęściej wystepują jako lewa strona redukcji w dowodach NP-zupełnosci. Poniżej definiujemy lub przypominamy grupe takich problemów, dość różnorodnego pochodzenia i zastosowania i dowodzimy ich NP-zupełności.

Najpierw 3SAT

Zaczynamy od sytuacji, w której jedynym znanym problemem NP-zupełnym (a więc możliwą lewą stroną redukcji) jest problem SAT. Jest on dość niewygodny jako problem źródłowy, redukcja z SAT do innego problemu na ogół wymaga skomplikowanego opisu. Okazuje się (wykazał to już Cook w swojej fundamentalnej pracy o NP-zupełności), że podproblem problemu SAT, w którym wymagamy, aby każda klauzula zawierała nie więcej niż 3 literały, jest sam w sobie NP-zupełny, a dowód tego faktu jest dość łatwy.

Twierdzenie 2.1

Problem 3SAT jest NP-zupełny.

Dowód

Problem 3SAT, jako podproblem problemu w klasie NP, sam należy do NP, zatem pierwsza część dowodu jest za nami.

Konstruujemy redukcję z problemu SAT do 3SAT. Na wejściu mamy formułe $\varphi =C_1\wedge \dots \wedge C_m$ nad zmiennymi $x_1,\dots ,x_n$. Każdą z klauzul $C_j$ przekształcamy osobno. Bez straty ogólności załóżmy, że $C_j=x_1\vee \dots \vee x_k$, gdzie $x_i,i=1,\dots ,k$ są parami różne. Jeśli $k\le 3$ to kładziemy $D_j=C_j$.

Niech $k>3$. Dodajemy $k-3$ nowych zmiennych $y_2,\dots ,y_{k-2}$, i zastepujemy $C_j$ przez

$D_j=(x_1\vee x_2\vee y_2)\wedge (\mathrm{\neg }{y}_2\vee x_3\vee y_3)\wedge (\mathrm{\neg }{y}_3\vee x_4\vee y_4)\wedge ...\wedge (\mathrm{\neg }{y}_{k-2}\vee x_{k-1}\vee x_k)$

Nietrudno spostrzec, że jeśli $C_j$ jest spełniona przez pewne wartościowanie zmiennych $x_1,\dots ,x_k$, to da się tak dobrać wartości dla zmiennych $y_2,\dots ,y_{k-2}$, aby spełnione były wszystkie klauzule w $D_j$. Na odwrót, jeśli $D_j$ jest spełniona dla pewnego wartościowania zmiennych $x_1,\dots ,x_k,y_2,\dots ,y_{k-2}$, to łatwo wydedukować, że $x_i=1$ dla pewnego $1\le i\le k$. Mianowicie, jeśli $x_1=x_2=0$, to z pierwszej klauzuli w $D_j$ wynika że $y_2=1$. Ale wtedy z drugiej klauzuli mamy $x_3=1$ lub $y_3=1$. W pierwszym przypadku rozumowanie jest zakończone, w drugim przenosimy rozumowanie na trzecią klauzulę i tak dalej.

Zatem, po przekształceniu kolejno wszystkich alternatyw powstaje równoważna formuła o co najwyżej trójskładnikowych alternatywach. Pozostaje wykazać, że przekształcenie to realizowalne jest w pamięci logarytmicznej. Zauważmy jednak, że aby wypisać formułę wynikową, MT potrzebuje pamięć roboczą tylko na licznik bieżącej alternatywy $C_j$ oraz licznik wygenerowanych do tej pory nowych zmiennych.

Uwaga 2.1

Zapewne zauważyłaś(-łeś), że w wielu podręcznikach do algorytmiki również mówi się o NP-zupełności. Na ogół korzysta się wtedy z redukcji wielomianowej. Złożoność czasowa jest łatwiejsza do analizy w przypadku modelu obliczeń takiego jak (uproszczony) język programowania wysokiego poziomu. Analiza złożoności pamięciowej (i to tylko z uwzględnieniem pamięci roboczej) może być trudniejsza.

Redukcja logarytmiczna jest bardziej uniwersalna i dlatego stosujemy ją w teorii złożoności.

Uwaga 2.2

W literaturze przyjmuje sie również nieco inną definicję problemu 3SAT, w której zakłada sie dodatkowo, że w każdej klauzuli występują dokładnie 3 parami różne literały. Dowód NP-zupełności tej wersji otrzymujemy przez uzupełnienie dowodu powyższego w następujący sposób:

Załóżmy że $k=2$. Wprowadzamy nową zmienną $y$ i kładziemy $D_j=(x_1\vee x_2\vee y)\wedge (x_1\vee x_2\vee \mathrm{\neg }y)$. Jeśli istnieje wartościowanie spełniające formułę $\varphi$, to w tym wartościowaniu formuła $\psi$ powstała z $\varphi$ przez zastąpienie klauzuli $C_j$ formułą $D_j$ jest również spełniona. I na odwrót, jeśli pewne wartościowanie spełnia formułę $\psi$, to aby $D_j$ było prawdziwe $x_1$ lub $x_2$ musi mieć wartość 1, a zatem to samo wartościowanie (bez zmiennej $y$) spełnia formułę $\varphi$.

Analogicznie, jesli $C_j$ składa się tylko z jednego literału, to przekształcamy go w koniunkcję czterech trójskładnikowych klauzul, z dodanymi dwiema nowymi zmiennymi.

Z tego spostrzeżenia będziemy korzystać w następnych dowodach NP-zupełności.

Odnotujmy w tym miejscu, że dalsze zawężenie problemu polegające na dopuszczeniu klauzul o co najwyżej dwóch literałach, 2SAT, jest problemem obliczeniowo łatwym. Dowód tego faktu odkładamy do następnej lekcji.

MAXSAT

Warto wspomnieć o innych NP-zupełnych wersjach problemu spełnialnosci. Na przykład, możemy zapytać o istnienie wartościowania spełniającego co najmniej zadaną liczbe $k$ klauzul (a niekoniecznie wszystkie). Problem ten nosi nazwę MAXSAT, i jest ogólniejszy niż SAT (a zatem jest również w NPC). Jego trudność przejawia sie również w tym, że zawężenie do klauzul długości dwa w przeciwieństwie do SAT, pozostawia ten problem trudnym.

Twierdzenie 2.2 [MAX2SAT]

Problem MAX2SAT jest NP-zupełny.

Dowód

Konstruujemy redukcję z problemu 3SAT. Na wejściu mamy formułę $\varphi =C_1\vee ...\vee C_m$. Każdą klauzulę $C_j=a\vee b\vee c$ przekształcamy w zbiór 10 klauzul, dla wygody rozważań podzielonych na trzy grupy, następujacej postaci:

1. $(a)(b)(c)(z)$
2. $(\mathrm{\neg }a\vee \mathrm{\neg }b)(\mathrm{\neg }b\vee \mathrm{\neg }c)(\mathrm{\neg }a\vee \mathrm{\neg }c)$
3. $(a\vee \mathrm{\neg }z)(b\vee \mathrm{\neg }z)(c\vee \mathrm{\neg }z)$

Tych 10 klauzul ma następujące własności:

1. Jeśli $a=b=c=0$, to niezależnie od wartości zmiennej $z$ co najwyżej 6 klauzul jest spełnionych.
2. Jeśli któryś z literałów $a$, $b$ lub $c$ jest równy 1, to

można dobrać wartość $z$ tak, że 7 klauzul jest spełnionych. Można sie o tym przekonać analizując wszystkie przypadki. Na przykład, jeśli $a=1$, $b=c=0$, to kładziemy $z=0$; jeśli $a=b=1$, $c=0$, to również kładziemy $z=0$, jeśli natomiast $a=b=c=1$ to 7 klauzul jest spełnionych gdy $z=1$.

Pozostaje zdefiniować żądaną liczbę spełnionych klauzul w formule wynikowej na $7m$. Z wymienionych własności wynika, że formuła wynikowa posiada wartościowanie spełniające dokładnie $7m$ alternatyw wtedy i tylko wtedy gdy formuła wejściowa jest spełnialna.

Maszyna Turinga realizująca redukcję potrzebuje pamieci roboczej jedynie na liczniki, zatem działa w pamięci logarytmicznej.

NP-zupełne problemy grafowe

Pokrycie wierzchołkowe

Pierwszym z serii problemów grafowych, dla których udowodnimy NP-zupełność, jest problem pokrycia wierzchołkowego. Dla grafu nieskierowanego $G=(V,E)$ mówimy, że podzbiór $V^{\prime }\subseteq V$ jest pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej jeden z końców w zbiorze $V^{\prime }$.

Problem [NODE COVER]

Wejście: Graf nieskierowany $G=(V,E)$, liczba całkowita $k\le |V|$

Wyjście: TAK jeśli G ma pokrycie wierzchołkowe o liczności k, NIE w przeciwnym przypadku.

Twierdzenie 3.1 [Problem NODE COVER]

Problem NODE COVER jest NP-zupełny.

Redukcja 3SAT do NODE COVER

Dowód

Dla podanego podzbioru zbioru wierzchołków bardzo łatwo sprawdzić, czy stanowi on pokrycie, zatem $NODECOVER\in NP$.

Redukujemy problem 3SAT do NODE COVER. Na wejściu mamy formułę $\varphi =C_1\wedge ...\wedge C_m$, i zgodnie z uwagą poczyniona przy dowodzie NP-zupełności 3SAT zakładamy, że każda alternatywa $C_j$ zawiera dokładnie 3 różne literały. Konstruujemy graf następujący: każde wystąpienie literału jest wierzchołkiem grafu, wystąpienia wewnątrz jednej klauzuli tworzą trójkąt. Ponadto, dla każdej pary literałów przeciwnych wystepujących w różnych klauzulach odpowiadające im wierzchołki łączymy krawędzią. Na koniec, kładziemy $k=2m$ (patrz rysunek Redukcja 3SAT do NODE COVER).

Teraz należy wykazać, że formuła wejsciowa jest spełnialna wtedy i tylko wtedy, gdy wygenerowany graf ma pokrycie wierzchołkowe o liczności $k$. Z ograniczenia na wielkość pokrycia wynika, że z każdego trójkąta do pokrycia muszą być wybrane dokładnie dwa wierzchołki. Jeśli formuła jest spełnialna, to w każdym trójkącie można wyróżnić jeden wierzchołek $v$ odpowiadający literałowi równemu 1. Do pokrycia wybieramy pozostałe dwa wierzchołki. Pokrywają one wszystkie krawędzie trójkątów oraz wychodzące z tych wierzchołków krawędzie między trójkątami. Każda pozostała krawędź, wychodząca z wierzchołka $v$, prowadzi do pewnego wierzchołka $w$ odpowiadającego zaprzeczeniu literału wierzchołka $v$, zatem literał wierzchołka $w$ ma wartość zero i $w$ jest wybrane do pokrycia w trójkącie, w którym występuje. Zatem krawędź $(v,w)$ też jest pokryta.

W drugą stronę, załóżmy, że dane jest pokrycie. W każdym trójkącie, dla wierzchołka, który nie jest w pokryciu, ustawiamy wartość odpowiedniej zmiennej tak, aby literał w tym wierzchołku był równy 1. Należy zauważyć, że takie wartościowanie jest niesprzeczne. Wynika to stąd, że przeciwne literały zawsze odpowiadają dwóm wierzchołkom z różnych trójkątów połączonych krawędzią. Co najmniej jeden z tych wierzchołków jest w pokryciu, a więc odpowiadający mu literał nie bierze udziału w obliczaniu wartościowania.

Zauważmy, że tak jak i poprzednio, do realizacji redukcji wystarczy pamięć robocza rzędu $n$, co kończy dowód.

Klika, zbiór niezależny

Przypomnijmy definicje obu problemów:

Problem [INDEPENDENT SET]

Wejście: Graf nieskierowany $G=(V,E)$, liczba całkowita $k\le |V|$

Wyjście: TAK jeśli $G$ ma zbiór niezależny (indukowany podgraf bez krawędzi) o $k$ wierzchołkach, NIE w przeciwnym przypadku.

Problem [CLIQUE]

Wejście: Graf nieskierowany $G=(V,E)$, liczba całkowita $k\le |V|$

Wyjście: TAK jeśli $G$ ma podgraf pełny (klikę) o $k$

wierzchołkach, NIE w przeciwnym przypadku.

Ćwiczenie 3.1

Wykaż, że problem INDEPENDENT SET jest NP-zupełny.

Wskazówka

Jeśli $V^{\prime }$ jest pokryciem wierzchołkowym, to jaką własność ma zbiór $V-V^{\prime }$?

Rozwiązanie

Dopełnienie pokrycia jest oczywiście zbiorem niezależnym. Zatem redukcja z problemu NODE COVER, mając na wejściu graf $G=(V,E)$ i liczbę $k$ generuje instancję $G^{\prime }=(V^{\prime },E^{\prime }),k^{\prime }$ problemu INDEPENDENT SET, kładąc $G^{\prime }=G$, $k^{\prime }=|V|-k$.

Ćwiczenie 3.2

Wykaż, że problem INDEPENDENT SET jest NP-zupełny, wykorzystując pokazaną wyżej redukcję z 3SAT do NODE COVER, zmieniając tylko rozumowanie tak, aby odnosiło sie do problemu INDEPENDENT SET.

Ćwiczenie 3.3

Wykaż, że problem CLIQUE jest NP-zupełny.

Wskazówka

Rozważ dopełnienie grafu.

Rozwiązanie

Redukcja z problemu INDEPENDENT SET. Graf wynikowy jest dopełnieniem grafu źródłowego, a parametr $k$ ma tę sama wartość.

Cykl i ścieżka Hamiltona

Problem [HAMILTONIAN CYCLE]

Wejście: Graf nieskierowany $G=(V,E)$

Wyjście: TAK jeśli $G$ ma cykl Hamiltona, czyli cykl przchodzący przez każdy wierzchołek dokładnie raz, NIE w przeciwnym przypadku.

Twierdzenie 3.2 [Cykl Hamiltona]

CYKL HAMILTONA jest NP-zupełny.

Gadżet dla HC.

Gadżety i cykl Hamiltona.

Ścieżki gadżetów i cykl Hamiltona.

Dowód

Przynależnośc do klasy NP jest oczywista. Konstruujemy redukcje z problemu NODE COVER. Na wejściu mamy nieskierowany graf $G=(V,E)$ oraz liczbę całkowitą $k\le |V|$. Oznaczmy graf wynikowy jako $G^{\prime }=(V^{\prime },E^{\prime })$.

Redukcja przeprowadzona jest techniką gadżetu (w literaturze angielskiej używa sie również terminu widget). Gadżet to fragment struktury wynikowej o określonych własnościach. W naszym przypadku pierwszym krokiem redukcji jest wygenerowanie, dla każdej krawędzi $(u,v)\in E$, gadżetu $G_{uv}=(V_{uv},E_{uv})$ będącego grafem przedstawionym na rysunku Gadżet dla HC.

Jedynie narożne wierzchołki grafu $G_{uv}$ będą połączone z wierzchołkami spoza $G_{uv}$. Stąd wynika, że jeśli $G^{\prime }$ ma cykl Hamiltona, to musi on przechodzić przez $G_{uv}$ tylko na jeden z przedstawionych na rysunku Gadżety i cykl Hamiltona sposobów. Konstrukcja gadżetu uniemożliwia inne usytuowanie cyklu Hamiltona względem $G_{uv}$ (rysunek Gadżety i cykl Hamiltona).

Drugi krok redukcji to wygenerowanie krawędzi w $G^{\prime }$ łączących gadżety w tak zwane ścieżki. Dla każdego wierzchołka $v\in V$ najpierw porządkujemy dowolnie wszystkie jego sąsiednie wierzchołki, oznaczmy je przez $u_v^1,\dots ,u_v^{d(v)}$, gdzie $d(v)$ jest stopniem wierzchołka $v$. Konstrukcja ścieżki odpowiadającej wierzchołkowi $v$, łączącej wszystkie gadżety odpowiadające krawędziom incydentnym z $v$, dokonuje się przez dołączenie do $G^{\prime }$ zbioru krawędzi postaci

$E_v=\{([v,u_v^i,6],[v,u_v^{i+1},1]),i=1,\dots ,d(v)-1\}$

Ostatni krok to dodanie wierzchołków-selektorów $s_1,\dots ,s_k$, i połączenie krawędzią każdego selektora z początkiem i końcem ścieżki odpowiadającej wierzchołkowi $v$, dla każdego $v$.

$E_S=\{(s_i,[v,u_v^1,1]):v\in V,1\le i\le k\}\{(s_i,[v,u_v^d(v),6]):v\in V,1\le i\le k$

Kładziemy zatem

$V^{\prime }=\bigcup _{(uv)\in E}{V}_{uv}\cup \{s_j,1\le j\le k\}$ $E^{\prime }=\bigcup _{(uv)\in E}{E}_{uv}\cup \bigcup _{v\in V}{E}_v\cup E_S$

W animacji Ścieżki gadżetów i cykl Hamiltona pokazano graf o 4 wierzchołkach i rezultat redukcji. Zacieniowane zostały dwa wierzchołki grafu, które tworzą pokrycie. Pogrubione krawędzie tworzą cykl Hamiltona. Zaczynając od selektora $s_1$, przechodzimy do początku ścieżki odpowiadającej pierwszemu wierzchołkowi z pokrycia, czyli $x$. Po przejściu gadżetów na tej ścieżce wracamy do $s_2$, a stąd do początku ścieżki odpowiadającej drugiemu węzłowi z pokrycia, $y$.

Wykażemy, że $G^{\prime }$ ma cykl Hamiltona wtedy i tylko wtedy, gdy $G$ ma pokrycie o liczności $k$.

Załóżmy, że $G^{\prime }$ ma cykl Hamiltona i prześledźmy jego bieg, zaczynając od $s_1$ (w dowolnym kierunku). Następny wierzchołek na cyklu musi być początkiem (lub końcem - załóżmy to pierwsze) ścieżki gadżetów dla pewnego wierzchołka $v_1\in V$. Dodajemy $v_1$ do generowanego pokrycia. Zgodnie z własnością gadżetu, cykl przebiega całą ścieżkę i na końcu przechodzi do innego selektora, załóżmy, że jest to $s_2$. Z $s_2$ musi przejść na początek lub koniec innej ścieżki, odpowiadającej wierzchołkowi $v_2$. Dodajemy $v_2$ do pokrycia i kontynuujemy. Z ostatniej, $k$-tej ścieżki, cykl musi wrócić do $s_1$. Ponieważ cykl Hamiltona przeszedł przez wszystkie wierzchołki $G^{\prime }$, a więc przez wszystkie gadżety $G_{uv}$, zatem wybrane w ten sposób wierzchołki $v_1,\dots ,v_k$ stanowią pokrycie.

Teraz załóżmy, że $G$ ma pokrycie $\{v_1,\dots ,v_k\}$. Konstruujemy cykl Hamiltona w $G^{\prime }$. Zaczynamy od selektora $s_1$ i przechodzimy na początek ścieżki związanej z $v_1$, czyli do węzła $[v_1,u_{v_1}^1,1]$. Przechodzimy przez kolejne gadżety aż do końca ścieżki. Dla danego gadżetu $G_{v_1{u}_{v_1}^i}$ musimy podjąć decyzję, czy przechodzimy przez wszystkie wierzchołki, czy tylko przez połowę (jedną "ścianę"). Decyzja zależy od tego, czy $u_{v_1}^i$ również należy do pokrycia. Jeśli nie, to przechodzimy cały gadżet; jeśli tak, to drugą "ścianę" pozostawiamy, aby później, gdy trawersowana będzie ścieżka dla $u_{v_1}^i$ również można było przejść przez $G_{v_1{u}_{v_1}^i}$. Z ostatniego węzła na ścieżce przechodzimy do selektora $s_2$ i powtarzamy konstrukcję. Z ostatniego węzła na $k$-tej ścieżce wracamy do $s_1$, zamykając w ten sposób cykl Hamiltona.

Ostatnim krokiem dowodu jest stwierdzenie, że konstrukcję grafu $G^{\prime }$ można wykonać, posługując się pamięcią roboczą rozmiaru logarytmicznego. Wynika to, jak i w poprzednich dowodach, z tego że maszynie wystarcza pamięć na licznik położenia w wejściowym grafie oraz licznik numeru (nazwy) generowanego wierzchołka i krawędzi grafu $G^{\prime }$.

Bardzo podobny w sformułowaniu jest problem ścieżki Hamiltona (HAMILTONIAN PATH). Na weściu jest graf nieskierowany, na wyjściu jest TAK, jeśli w grafie istnieje ścieżka przechodząca przez każdy wierzchołek dokładnie raz. Oczywiste jest, że istnienie cyklu Hamiltona implikuje istnienie ścieżki Hamiltona, jednak są to różne problemy, i NP-zupełność tego drugiego wymaga osobnego dowodu. Tym niemniej, na przykładzie tych problemów można pokazać pewne techniki dowodzenia NP-zupełności w takich przypadkach. Jedną z nich jest modyfikacja znanego już dowodu NP-zupełności problemu podobnego, drugą zaś redukcja z problemu podobnego.

Twierdzenie 3.3 [HAMILTONIAN PATH]

Problem HAMILTONIAN PATH jest NP-zupełny.

Ćwiczenie 3.4

Metoda 1: zmodyfikuj konstrukcję grafu $G^{\prime }$ w dowodzie NP-zupełności problemu HAMILTONIAN CYCLE tak, aby stanowił dowód NP-zupełności problemu HAMILTONIAN PATH.

Wskazówka

Należy "wymusić" rozpoczęcie i zakończenie ścieżki dodatkowymi selektorami.

Rozwiązanie

Dodajemy selektor $s_0$ i łączymy go krawędzią z $s_1$. Następnie dodajemy selektor $s_{k+1}$ i łączymy go z początkami i końcami wszystkich ścieżek. Na koniec dodajemy $s_{k+2}$ i łączymy go z $s_{k+1}$. Jeśli graf wynikowy posiada ścieżkę Hamiltona, to jej końcami muszą być selektory $s_0$ i $s_{k+2}$. Pozostała część rozumowania jest analogiczna.

Ćwiczenie 3.5

Metoda 2: Skonstruuj redukcję z problemu CYKL HAMILTONA.

Wskazówka

Dodaj nowe wierzchołki które będą końcami ścieżki Hamiltona i powiąż je odpowiednio z innymi wierzchołkami.

Rozwiązanie

Nie prowadzi do celu narzucający się pomysł, aby dowiązać 2 nowe wierzchołki do końców dowolnie ustalonej krawędzi. Skuteczna jest natomiast modyfikacja tej idei: wybrać dowolny wierzchołek $v$, utworzyć wierzchołek $v^{\prime }$ o takim samym zbiorze sąsiadów w grafie (inaczej: rozszczepić v na dwa identyczne), a następnie dołączyć nowy wierzchołek $u_1$ do $v$ i jeszcze jeden nowy $u_2$ do $v^{\prime }$.

Łatwo się przekonać, że w nowym grafie istnieje ścieżka Hamiltona (koniecznie o końcach $u_1,u_2$) wtedy i tylko wtedy, gdy w oryginalnym grafie istnieje cykl Hamiltona.

Problemy na zbiorach i liczbach

Trójdzielne skojarzenie i pokrycie zbiorami

Uogólnieniem klasycznego problemu skojarzenia w grafie dwudzielnym jest następujący problem:

Problem [TRIPARTITE MATCHING]

Wejście: parami rozłączne równoliczne zbiory $W,X,Y$ o mocy $p>0$ oraz relacja $R\subseteq W\times X\times Y$
Wyjście: TAK, jeśli istnieje skojarzenie w $R$, czyli podzbiór $R^{\prime }\subseteq R$ taki, że dla dowolnych trójek $(w,x,y),(w^{\prime },x^{\prime },y^{\prime })\in R$ zachodzi $w\ne w^{\prime }$, $x\ne x^{\prime }$ oraz $y\ne y^{\prime }$. NIE w przeciwnym przypadku.

Problem skojarzenia dwudzielnego jest obliczeniowo łatwy. Uogólnienie do trzech wymiarów utrudnia problem radykalnie.

Twierdzenie 4.1 [TRIPARTITE MATCHING]

Problem TRIPARTITE MATCHING jest NP-zupełny.

Gadżet redukcji 3SAT do 3DM.

Dowód

Ponownie mamy do czynienia z dość skomplikowaną konstrukcją posługującą się gadżetami, redukującą problem 3SAT do naszego problemu.

Na wejściu mamy zbiór klauzul $C=\{C_1,\dots ,C_m\}$ nad zmiennymi $U=\{u_1,\dots ,u_n\}$. Najpierw dla każdej zmiennej $u\in U$ konstruujemy gadżet $T_u$, który będzie odpowiadał za wybór wartościowania tej zmiennej. Składa się on z dwóch zbiorów trójek:

$T_u^t=\{(w_{2j}^u,x_j^u,y_j^u),1\le j\le m\}$

$T_u^f=\{(w_{2j+1}^u,x_{j+1}^u,y_j^u),1\le j<m\}\cup \{(w_1^u,x_1^u,y_m^u)\}$

Przykładowy gadżet dla zmiennej $u$ w przypadku, gdy liczba klauzul wynosi $m=4$ pokazano na rysunku Gadżet redukcji 3SAT do 3DM. Grubą linią zaznaczono trójki ze zbioru.

Dla każdego gadżetu pierwsze elementy trójek, $w_1^u,\dots ,w_m^u$, występują jeszcze w innych trójkach, które za chwilę zdefiniujemy. Pozostałe elementy występują tylko w danym gadżecie. Zatem, jeśli wybrano skojarzenie, to dla ustalonego gadżetu to skojarzenie zawiera albo cały zbiór $T_u^f$ i żadnej trójki z $T_u^t$, albo na odwrót. W toku dalszego rozumowania, wybór do skojarzenia zbioru $T_u^f$ będzie oznaczał wartościowanie zmiennej $u$ na false i pozostawi niepokryte elementy $w$ o indeksach parzystych. Wybór przeciwny ustali wartościowanie $u$ na true i pozostawi niepokryte elementy $w$ o indeksach nieparzystych. Sytuacja taka została przedstawiona na rysunku Gadżet redukcji 3SAT do 3DM, pogrubioną linią zaznaczono wybór trójek $T_u^t$.

Trójki, które zdefiniujemy, teraz mogą być nazwane "składową testowania". Skojarzą one niepokryte elementy z gadżetów z odpowiednimi wystąpieniami literałów w klauzulach. Dla każdej klauzuli $C_j=(p_j\vee q_j\vee r_j)$ składowa testowania $S_j$ zawiera 3 trójki $s_j^1,s_j^2,s_j^3$ odpowiadajace kolejnym literałom $p,q,r$, zdefiniowane następująco: Jeśli $p=u_i$ to $s_j^1=(w_{2j-1}^u,a_j,b_j)$. Jeśli $p=\mathrm{\neg }{u}_i$ to $s_j^1=(w_{2j}^u,a_j,b_j)$. Analogicznie dla literałów $q,r$.

Elementy $a_j,b_j$ występują tylko w trzech trójkach zbioru $S_j$, zatem skojarzenie wybiera dokładnie jedną z tych trójek. Aby móc daną trójkę wybrać, element na pierwszej współrzędnej w tej trójce musi być niepokryty trójkami z odpowiedniego gadżetu. Ale to oznacza, że wartość danego literału jest true, czyli klauzula $C_j$ jest spełniona. Innymi słowy, możliwość pokrycia elementów $a_j,b_j$ jest równoważna temu, że istnieje w klauzuli $C_j$ literał o wartości logicznej true.

Skojarzenie wybrane dla gadżetów ma liczność $nm$, składowa testowania daje kolejnych $m$ trójek w skojarzeniu, zatem ze wszystkich $2nm$ elementów na pierwszej współrzędnej (elementy $u$)$(n-1)m$ pozostaje nieskojarzonych. Zatem w konstrukcji potrzebna jest jeszcze trzecia "składowa odśmiecania" zdefiniowana nastepująco:

$G=\{(w_i^u,g_k,h_k):u\in U,1\le i\le 2m,1\le k\le (n-1)m\}$

Pozwala ona skojarzyć elementy $u$ pozostałe po wyborze wartościowania i testu spełnialności.

Na podstawie opisanej konstrukcji i komentarzy jej towarzyszących możemy już łatwo stwierdzić, że formuła wejściowa posiada wartościowanie spełniające wtedy i tylko wtedy, gdy utworzony w wyniku redukcji zbiór trójek ma skojarzenie.

Rozważmy jeszcze trzy podobne problemy na zbiorach. Ich NP-zupełność stanie się oczywista, gdy zauważymy, że stanowią one kolejne uogólnienia problemu trójdzielnego skojarzenia.

Problem [EXACT COVER BY 3-SETS (pokrycie trójelementowymi podzbiorami)]

Wejście: Rodzina ${ℱ}$ trójelementowych podzbiorów zbioru $X$, takiego że $|X|=3k$ dla pewnej calkowitej $k$
Wyjście: TAK, jeśli istnieje podrodzina ${{ℱ}}^{\prime }\subseteq {ℱ}$ taka, że każdy element zbioru $X$ należy do dokładnie jednego zbioru rodziny ${{ℱ}}^{″}$, NIE w przeciwnym przypadku.

Ćwiczenie 4.1

Wykaż że EXACT COVER BY 3-SETS jest NP-zupełny.

Rozwiązanie

Zauważ, że jeśli ograniczymy się do instancji, w których X jest podzielone na trzy rozłączne równoliczne zbiory, a wszystkie podzbiory w rodzinie $F$ zawierają po jednym elemencie z każdego z tych trzech podzbiorów, to otrzymujemy problem TRIPARTITE MATCHING (formalnie są to izomorficzne struktury). Zatem EXACT COVER BY 3-SETS jest uogólnieniem TRIPARTITE MATCHING, a ponieważ, co oczywiste, jest w NP, więc jest NP-zupełny.

Problem [SET COVERING (pokrycie zbiorami)]

Wejście: Rodzina $F=\{S_1,\dots ,S_n\}$ podzbiorów zbioru $|X|$, liczba całkowita $k\le n$
Wyjście: TAK, jeśli istnieje k-elementowa podrodzina rodziny $F$, która pokrywa cały zbiór $|X|$, w przeciwnym przypadku NIE.

Ćwiczenie 4.2

Wykaż NP-zupełność problemu SET COVERING.

Rozwiązanie

Ponownie przez ograniczenie do podproblemu: jeśli założymy że $|X|=3k$ a wszystkie zbiory rodziny $F$ są 3-elementowe, to otrzymujemy problem EXACT COVER BY 3-SETS.

Suma podzbioru i inne problemy liczbowe

Teraz zajmiemy się kilkoma problemami związanymi z liczbami. Najwięcej trudu będzie kosztować udowodnienie NP-zupełności pierwszego z nich - następne pójdą już łatwiej. Ta pierwsza trudność zasadza się na tym, że jak do tej pory dowodziliśmy NP-zupełność tylko dla problemów, w których tak naprawdę nie ma liczb, jako elementów struktury kombinatorycznej. Oczywiście, każde słowo wejściowe może być traktowane jako liczba, kod maszyny Turinga też jest liczbą. Tutaj jednak chodzi o naturalne sformułowanie problemu, w odniesieniu do obiektów abstrakcyjnych takich, jak: liczby, funkcje, relacje, grafy itd. Problematyka trudności obliczeniowej problemów z liczbami jest rozwinięta w następnej lekcji.

Problem [SUBSET SUM (suma podzbioru)]

Wejście: Skończony zbiór $A$ elementów, dla każdego elementu $a\in A$ waga $s(a)\in Z^{+}$ oraz liczba $B\in Z^{+}$.
Wyjście: TAK, jeśli istnieje podzbiór $A^{\prime }\subseteq A$ taki że $\sum _{a\in A^{\prime }}s(a)=B$, NIE w przeciwnym przypadku.

Twierdzenie 4.2 [SUBSET SUM]

Problem SUBSET SUM jest NP-zupełny.

Dowód

Skonstruujemy redukcję z problemu EXACT COVER BY 3 SETS. Na wejściu mamy zatem zbiór $X$ o liczności $3m$ i rodzinę $F=\{U_1,\dots ,U_n\}$ jego podzbiorów. Naszym zadaniem jest skonstruować zbiór $Y$ elementów z pewnymi wagami oraz liczbę B taką, że istnienie podzbioru w $Y$ o sumie wag elementów równej $B$ "wymusza" istnienie pokrycia zbioru $X$ wybranymi rozłącznymi podzbiorami z rodziny $F$.

Niech $p=\lceil {\log }_2(n+1)\rceil$. Najpierw ustalamy porządek elementów w zbiorze $|X|$ i zapisujemy każdy zbiór $U_j$ jako wektor $3m$-bitowy (czyli jest to struktura danych - wektor bitowy - reprezentująca podzbiór danego zbioru). W każdym wektorze są oczywiście 3 bity równe 1 a pozostałe są zerowe. Następnie przed każdym bitem wstawiamy dodatkowo $p-1$ bitów zerowych i traktujemy ten wektor jako liczbę zapisaną binarnie. Powstaje w ten sposób $n$ liczb $3mp$-bitowych - są to wagi elementów zbioru Y. Liczba $B$ jest również takiej długości, powstaje przez wypisanie $3m$ jedynek, a następnie wstawienie przed każdą jedynką $p-1$ zer.

Jeśli istnieje podrodzina $F^{\prime }\subseteq F$ stanowiąca rozłączne pokrycie zbioru $X$, to wektory bitowe poszczególnych trójek z $F^{\prime }$ arytmetycznie sumują sie do $B$, a na żadnej pozycji nie występuje przeniesienie. Zatem z istnienia pokrycia wynika istnienie podzbioru dającego w sumie wagę $B$.

Bloki zer dodane przed każdym bitem reprezentacji wektorowej podzbioru gwarantują, że sumując dowolny podzbiór wygenerowanych liczb, nie napotkamy na przeniesienie poza taki blok zer. A zatem, jeśli istnieje podzbiór liczb dający w sumie $B$, to wszystkie te liczby w swoich rozwinięciach binarnych zawierają w sumie tyle jedynek, ile jest ich w $B$, na różnych pozycjach. A więc odpowiadajace tym liczbom podzbiory pokrywają cały zbiór $X$.

Zatem opisane przekształcenie jest redukcją. Jak w poprzednich dowodach, potrzebna jest pamięć robocza jedynie na stałą liczbę liczników. A więc jest to redukcja logarytmiczna.

W tej części lekcji wykażemy NP-zupełność dwóch podobnych problemów liczbowych.

Problem [PARTITION (podział)]

Wejście: Skończony zbiór $A$ elementów oraz dodatnia całkowita waga $s(a)$ każdego elementu.
Wyjście: TAK, jeśli istnieje podzbiór $A^{\prime }\subseteq A$, taki że $\sum _{a\in A^{\prime }}s(a)=\sum _{a\in A-A^{\prime }}s(a)$, NIE w przeciwnym przypadku.

Ćwiczenie 4.3

Wykaż NP-zupełność problemu podziału.

Wskazówka

Skorzystaj z SUBSET SUM. Wystarczy dodać dwa elementy o odpowiednio dobranej dużej wadze.

Rozwiązanie

Niech $S=\sum _{a\in A}s(a)$. Dodajemy do zbioru dwa elementy $b_1$ i $b_2$, $s(b_1)=2S-B,s(b_2)=S+B$. Łatwo sprawdzić, że:

• jeśli w zbiorze $A$ istnieje podzbiór $A^{\prime }$ o sumie równej $B$, to podzbiór ten z dołączonym elementem $b_1$ daje sumę równą $2S$, tyle co pozostałe elementy uzupełnione o $b_2$,

• jeśli w zbiorze $A\cup \{b_1,b_2\}$ istnieje podział na 2 podzbiory o jednakowych wagach, to elementy $b_1$ i $b_2$ są w różnych podzbiorach, bo ich wagi sumują się do $3S$. W tym podzbiorze, do którego należy $b_1$ suma wag pozostałych elementów wynosi $B$.

Problem [KNAPSACK (plecak)]

Wejście: Skończony zbiór $A$ elementów, rozmiar $s(a)\in Z^{+}$ i wartość $v(a)\in Z^{+}$ dla każdego elementu, ograniczenie pojemności $B\in Z^{+}$ oraz żądana wartość $K\in Z^{+}$.
Wyjście: TAK, jeśli istnieje podzbiór $A^{\prime }\subseteq A$, taki że $\sum _{a\in A^{\prime }}s(a)\le B$ oraz $\sum _{a\in A}v(a)\ge K$, NIE w przeciwnym przypadku.

Ćwiczenie 4.4

Pokaż że KNAPSACK jest NP-zupełny.

Wskazówka

Wykorzystaj SUBSET SUM lub PARTITION.

Rozwiązanie

Jeśli założymy, że rozmiary elementów są równe ich wartościom, a pojemność plecaka jest równa żądanej wartości, to otrzymamy problem SUBSET SUM.

Podsumowanie technik dowodów NP-zupełności

Najprostsze redukcje otrzymujemy metodą zacieśnienia. Przez narzucenie dodatkowych zależności w instancjach problemu, o którym dowodzimy NP-zupełności, otrzymujemy instancje znanego problemu NP-zupełnego. W ten sposób wykazujemy, że nasz problem jest uogólnieniem problemu znanego, a więc nie jest od niego łatwiejszy. Przykłady takich redukcji zastosowaliśmy do problemów: EXACT COVER BY 3SETS, SET COVERING, KNAPSACK.

Pozostałe dowody można by zaliczyć do metody gadżetów. Fragmenty instancji problemu wejściowego przekształca się we fragmenty instancji probelmu wynikowego (gadżety) i wiąże się zależnościami (innymi gadżetami), których zachodzenie w problemie wynikowym ma mieć ścisłe odzwierciedlenie w spełnieniu wymagań problemu źródłowego. Czasem gadżet jest trywialny (np. w redukcji SUBSET SUM do PARTITION jest to ta sama waga elementu), kiedy indziej dość naturalny i nietrudny (SAT DO 3SAT), czasem bardzo pomysłowy (VERTEX COVER do HAMILTONIAN CYCLE, 3SAT do TRIPARTITE MATCHING, 3SAT do MAX2SAT).

Ćwiczenia końcowe

Ćwiczenie 6.1

Wykaż, że następujący problem izomorfizmu podgrafu jest NP-zupełny:

Problem [SUBGRAPH ISOMORPHISM]

Wejście: $G_1=(V_1,E_1)$, $G_2=(V_2,E_2)$ - grafy nieskierowane.
Wyjście: TAK, jeśli $G_1$ ma podgraf izomorficzny z $G_2$, NIE w przeciwnym przypadku.

Wskazówka

Istnieje redukcja najprostszego typu z jednego z analizowanych powyżej problemów.

Rozwiązanie

Jest to proste ugólnienie problemu CLIQUE: szczególnym przypadkiem podgrafu, o który pytamy w problemie SUBGRAPH ISOMORPHISM jest klika o liczności $k$, o którą pytamy w problemie CLIQUE.

Ćwiczenie 6.2

W tym ćwiczeniu pytamy o trudność obliczeniową problemu pochodzącego z teorii szergowania. Wykaż, że NP-zupełny jest następujący problem:

Problem [SEQUENCING WITHIN INTERVALS]

Wejście: Zbiór zadań $T$, dla każdego zadania $t$ trzy liczby całkowite: długość zadania $l(t)>0$, moment pojawienia się $r(t)\ge 0$,oraz ograniczenie czasowe $d(t)>0$
Wyjście: TAK, jeśli wszystkie zadania można wykonać na jednym procesorze, bez przerywania, spełniając ograniczenia czasowe, NIE w przeciwnym przypadku. Formalnie, pytamy o funkcję alokacji $A$ przydzielająca każdemu zadaniu $t$ czas rozpoczęcia wykonywania $A(t)$ taki, że $[A(t),A(t)+l(t)]\subseteq [r(t),d(t)]$ oraz $[A(t),A(t)+l(t))\cap [A(t^{\prime }),A(t^{\prime })+l(t^{\prime }))=\mathrm{\varnothing }$, dla każdego zadania $t^{\prime }\ne t$.

Wskazówka

Spróbuj, układając na prostej (osi liczbowej) odpowiednio zdefiniowany ciąg odcinków (zadań), wymusić istnienie podzbioru o zadanej sumie.

Rozwiązanie

Redukcja z problemu SUBSET SUM za pomocą bardzo prostych gadżetów. Niech $s_1,\dots ,s_n$ oraz $B$ będą odpowiednio wagami elementów oraz żądaną sumą podzbioru elementów. Niech $D=\sum _{i=1}^n{s}_i$. Konstruujemy $n+1$ zadań, przy czym dla $i=1,\dots ,n$ zadanie $t_i$ ma długość $l_i=s_i$, czas gotowości $r_i=0$ oraz granicę $d_i=D+1$. Zadanie $t_{n+})$ jest "wymuszaczem podziału" o parametrach $l_i=1$, $r_i=B$, $d_i=B+1$.

Zadania $s_1,\dots ,s_n$ mają pozorną swobodę wykonywania sie w dowolnym miejscu osi czasu, zauważmy jednak, że każde ulokowanie wszystkich zadań nie zostawia żadnej luki na osi. Dla wymuszacza jest tylko jedna możliwa wartość alokacji, $B$. Takie położenie dzieli cały przedział, w którym mogą być wykonywane zadania, na dwa podprzedziały, rozdzielone wymuszaczem. Jeden z tych przedziałów ma długość $B$, zatem ulokowanie zadań na osi, zgodne z warunkami zadania, jest możliwe wtedy i tylko wtedy, gdy istnieje podzbiór zbioru elementów w instancji problemu SUBSET SUM, których wagi dają w sumie $B$.

Ćwiczenie 6.3

Problem cięcia w grafie zdefiniowany jest następująco:

Problem [FEEDBACK VERTEX SET]

Wejście: Graf skierowany $G=(V,E)$, liczba całkowita $k,0<k\ge |V|$.
Wyjście: TAK, jeśli istnieje w $G$ podzbiór $k$-wierzchołkowy, taki że graf pozostały po usunięciu tego podzbioru jest acykliczny.
Udowodnij, że FEEDBACK VERTEX SET jest NP-zupełny.

Wskazówka

Jak zwykle, najtrudniej dobrać problem źródłowy dla redukcji. Proponujemy pokrycie wierzchołkowe. Jak powinien wyglądać wynik redukcji -- graf skierowany -- aby rozcinanie wszsytkich cykli przez usuwanie wierzchołków znaczyło to samo, co definiowanie pokrycia w grafie źródłowym?

Rozwiązanie

Na wejściu mamy graf nieskierowany $G=(V,E)$ i liczbę $k$. Zamieniamy ten graf na graf skierowany $G^{\prime }$, z tym samym zbiorem wierzchołków, zastępując każdą krawędź nieskierowaną $(u,v)$ przez dwie krawędzie skierowane: $(u,v)$ oraz $(v,u)$. Liczba $k$ jest taka sama dla obu instancji.

Nietrudno zauważyć, że każde pokrycie wierzchołkowe w $G$ jest zbiorem rozcinającym wszystkie cykle w $G^{\prime }$ i na odwrót.

Ćwiczenie 6.4

Kolorowanie (wierzchołkowe) grafu jest klasycznym problemem optymalizacyjnym w teorii grafów. Przypomnijmy, że chodzi o przypisanie wierzchołkom grafu nieskierowanego kolorów tak, aby końce każdej krawędzi miały różne kolory, a liczba kolorów była możliwie najmniejsza.

Okazuje sie że nawet jeśli ustalimy żądaną liczbe kolorów na 3, to problem jest NP-zupełny. Dowód tego faktu nie jest natychmiastowy.

Problem [3COLORING]

Wejście: Graf nieskierowany $G=(V,E)$.
Wyjście: TAK, jeśli istnieje funkcja $c:V\to \{0,1,2\}$ taka, że dla każdej krawędzi $(u,v)\in E$, $c(u)\ne c(v)$.
Za pomocą redukcji z problemu 3SAT udowodnij, że problem trójkolorowania jest NP-zupełny.

Wskazówka

Można użyć gadżetu przedstawionego na Rysunku 5.6.

Rysunek 5.6.

Rozwiązanie

Gadżet ma następujące własności:

• jeśli wierzchołkom $u,v,z$ przypisano kolory tak, że co najmniej jeden z nich ma kolor 1, to istnieje uzupełnienie trójkolorowania pozostałych wierzchołków takie, że $c(z)=1$

• jeśli w danym trójkolorowaniu $c(u)=c(v)=c(z)=0$, to również $c(z)=0$.

Load video

Local File

Local File might collect personal data.

Continue Dismiss

Animacja 5.7.

Redukcję przeprowadzamy następująco:

1. generujemy wierzchołki $s,t,z$ i trójkąt oparty na nich,
2. dla każdej zmiennej $x$ występującej w instancji 3SAT definiujemy wierzchołki $x,\mathrm{\neg }x$ oraz trójkąt oparty na $x,\mathrm{\neg }x$ oraz $t$,
3. dla każdej klauzuli $C_j=(u\vee v\vee w)$ definiujemy kopię gadżetu, przy czym wierzchołki $u,v,w$ to już wygenerowane w punkcie 2 wierzchołki literałów o tych samych nazwach, wierzchołek $z$ został wygenerowany w kroku 1, natomiast pozostałe wierzchołki są nowe, unikalne dla każdej klauzuli.

Wykażemy, że formuła źródłowa ma spełniające wartościowanie wtedy i tylko wtedy, gdy wygenerowany graf można pokolorować trzema kolorami.

Jeśli istnieje wartościowanie spełniające formułę, to

• kładziemy $c(s)=0$, $c(z)=1$ $c(t)=2$,
• kolorujemy każdy z wierzchołków $x_i,\mathrm{\neg }{x}_i$ jego wartością logiczną, 0 lub 1,
• uzupełniamy kolory 0, 1, i 2 w gadżetach - można to zrobić gdyż zadane wartościowanie spełnia formułę, a więc na wejściu do każdego gadżetu jest co najmniej jeden wierzchołek koloru 1.

Jeśli zadane jest trójkolorowanie grafu, to obliczamy wartościowanie spełniające formułę następująco:

• kolory wierzchołków $s,t,z$ są różne, więc umawiamy się, że $c(s)=0,c(t)=2,c(z)=1$,
• dla każdej zmiennej $x_i$ kładziemy wartość tej zmiennej równą $c(x_i)$. Ponieważ $c(t)=2$ więc wartość ta wynosi 0 lub 1.

Ponieważ $c(z)=1$, więc dla każdego gadżetu co najmniej jeden z jego trzech wejściowych wierzchołków ma kolor 1, a zatem w każdej klauzuli mamy co najmniej jedną jedynkę.