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<nowiki>=</nowiki>1$ dla pewnego $1ik$. Mianowicie, jeśli $x_1<nowiki>=</nowiki>x_2<nowiki>=</nowiki>0$, to z pierwszej klauzuli w $D_j$ wynika że $y_2<nowiki>=</nowiki>1$. Ale wtedy z drugiej klauzuli mamy $x_3<nowiki>=</nowiki>1$ lub $y_3<nowiki>=</nowiki>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<nowiki>=</nowiki>2$. Wprowadzamy nową zmienną $y$ i kładziemy $D_j<nowiki>=</nowiki>(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łę Parser nie mógł rozpoznać (błąd składni): {\displaystyle <math>, to w tym wartościowaniu formuła } Parser nie mógł rozpoznać (błąd składni): {\displaystyle powstała z } Parser nie mógł rozpoznać (błąd składni): {\displaystyle przez zastąpienie klauzuli <math>C_j} formułą </math>D_jParser nie mógł rozpoznać (błąd składni): {\displaystyle jest również spełniona. I na odwrót, jeśli pewne wartościowanie spełnia formułę <math>\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 </math>C_jParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } kParser nie mógł rozpoznać (błąd składni): {\displaystyle 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|[Uzupelnij]|| Problem MAX2SAT jest NP-zupełny. }} {{dowod|[Uzupelnij]|| Konstruujemy redukcję z problemu 3SAT. Na wejściu mamy formułę } =C_1 ... C_mParser nie mógł rozpoznać (błąd składni): {\displaystyle . Każdą klauzulę } C_j=a b cParser nie mógł rozpoznać (błąd składni): {\displaystyle przekształcamy w zbiór 10 klauzul, dla wygody rozważań podzielonych na trzy grupy, następujacej postaci: # } (a)(b)(c)(z)Parser nie mógł rozpoznać (błąd składni): {\displaystyle # } ( a b)( b c)( a c)Parser nie mógł rozpoznać (błąd składni): {\displaystyle # } (a z)(b z)(c z)Parser nie mógł rozpoznać (błąd składni): {\displaystyle Tych 10 klauzul ma następujace własności: # Jeśli } a=b=c=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle , to niezależnie od wartości zmiennej } zParser nie mógł rozpoznać (błąd składni): {\displaystyle co najwyżej 6 klauzul jest spełnionych. # Jeśli któryś z literałów } a$,$b$lub$cParser nie mógł rozpoznać (błąd składni): {\displaystyle jest równy 1, to można dobrać wartość } zParser nie mógł rozpoznać (błąd składni): {\displaystyle 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=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle , to kładziemy } z=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle ; jeśli } a=b=1$,$c=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle , to również kładziemy } z=0Parser nie mógł rozpoznać (błąd składni): {\displaystyle , jeśli natomiast } a=b=c=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle to 7 klauzul jest spełnionych gdy } z=1Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Pozostaje zdefiniować żądaną liczbę spełnionych klauzul w formule wynikowej na } 7mParser nie mógł rozpoznać (błąd składni): {\displaystyle . Z wymienionych własności wynika, że formuła wynikowa posiada wartościowanie spełniające dokładnie } 7mParser nie mógł rozpoznać (błąd składni): {\displaystyle 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)Parser nie mógł rozpoznać (błąd składni): {\displaystyle mówimy, że podzbiór } V' VParser nie mógł rozpoznać (błąd składni): {\displaystyle jest pokryciem wierzchołkowym, jeśli każda krawędź w G ma co najmniej jeden z końców w zbiorze } V'Parser nie mógł rozpoznać (nieznana funkcja „\bigskip”): {\displaystyle . \bigskip \noindent {\bf Problem} NODE COVER\\ {\it Wejście:} Graf nieskierowany } G=(V,E)Parser nie mógł rozpoznać (błąd składni): {\displaystyle , liczba całkowita } k

Rozważmy jeszcze trzy podobne problemy na zbiorach. Ich NP-zupełność stanie sie 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 jesli istnieje podrodzina ${{ℱ}}^{\prime }{\subseteq }{ℱ}$ taka, że każdy element zbioru $X$ należy do dokładnie jednego zbioru rodziny Parser nie mógł rozpoznać (błąd składni): {\displaystyle \cal F"} , NIE w przeciwnym przypadku

section

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

Rozwiązanie

Zauważ, że jeśli ograniczymy sie do instancji w których X jest podzielone na trzy rozłączne równoliczne zbiory, a wszystkie podzbiory w rodzinie $F$ zawieraja 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.

section

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 byc traktowane jako liczba, kod maszyny Turinga tez 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 [Uzupelnij]

Problem SUBSET SUM jest NP-zupełny.

Dowód [Uzupelnij]

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 kjako liczbe 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.

section

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

section

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śc 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 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ę.