Złożoność obliczeniowa/Wykałd 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ą ta 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 niz 3 literały jest sam w sobie NP-zupełny, a dowód tego faktu jest dość łatwy.

Twierdzenie

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,...,x_k$, to da się tak dobrać wartości dla zmiennych $y_2,...,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,...,x_k,y_2,...,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 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

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 nastepnej 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 [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)$

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

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

Tych 10 klauzul ma następujace 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.

1. 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 [Problem NODE COVER]

Problem NODE COVER jest NP-zupełny.

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$.

rys_5_1.jpg(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.

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 [Cykl Hamiltona]

CYKL HAMILTONA jest NP-zupełny.

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 uzywa 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 5.2.

rys_5_2.jpg

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 5.3 sposobów. Konstrukcja gadżetu uniemożliwia inne usytuowanie cyklu Hamiltona względem $G_{uv}$.

rys_5_3.jpg

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,...,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 sie 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$

rys_5_4.jpg

Na rys. 5.4 pokazano graf o 4 wierzchołkach i rezultat redukcji. Zacieniowane zostały dwa wierzchołki grafu które tworzą pokrycie. Pogrubione krawędzie tworza 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 odpowiadajacej 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,...,v_k$ stanowią pokrycie.

Teraz załóżmy, że $G$ ma pokrycie $\{v_1,...,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śc tego drugiwgo 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 [HAMILTONIAN PATH]

Problem HAMILTONIAN PATH jest NP-zupełny.

Ćwiczenie

{{{3}}}

Ćwiczenie

{{{3}}}

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 jest nieł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

ż, ż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óra pytamy w problemie CLIQUE.

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 żądana 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 moga byc 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, ktych wagi dają w sumie $B$.

section

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.

section

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. {1cm}

[width=12cm]{rys_5_6.jpg}

{1cm} UWAGA DLA REDAKCJI: RYSUNEK POJAWIA SIĘ JAKO CZĘŚĆ WSKAZÓWKI

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$.

Redukcję przeprowadzamy następująco:

1. generujemy wierzchołki $s,t,z$ i trójkat oparty na nich

1. 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$

1. 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

{1cm}

[width=12cm]{rys_5_7.jpg}

{1cm}

Wykazemy, ż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ę.