NP-úplné problémy.

Ciele

Zvládnuť základné definície
Vedieť rozlíšiť, či daný kombinatorický problém patrí do triedy NP.
Metodicky zvládnuť dokazovanie NP-úplnosti.

Postup

Úloha: Problém obchodného cestujúceho (Traveling Salesman Problem -- TSP) V individuálnej úlohe TSP je dané prirodzené číslo $ n>0 $ a matica vzdialeností medzi každou dvojicou $ n $ miest vo forme $ n\times n $ matice $ (d_{ij}) $, $ d_{ij}\in Z^+ $ ($ Z^+ $ je označenie pre kladné celé čísla).
Problém: Nájsť uzavretú cestu, ktorá prechádza každým mestom práve raz, a pritom zo všetkých takýchto ciest má minimálny súčet ohodnotení hrán.

Úloha: Uvažujme o nasledujúcom kombinatorickom probléme, nazývanom problém maximálnej kliky (Clique Problem - CP) Pre daný graf $G=(V,E)$, nájdite najväčšiu podmnožinu $C\subset V$ takú, že pre všetky rôzne $u,v\in C$ platí $(u,v)\in E$.\\ Parameter $S$ je v tomto prípade graf $G$. Pre daný graf $G=(V,E),\ {\cal A_F}$ rozhodne, či $f$ tvorí kliku v $G$, t.j. úplný podgraf na $C$. ${\cal A_C}$ vypočíta veľkosť $f$ (teda mohutnosť $f$), $Q=\emptyset$ pre tento prípad.

Úloha: Problém splniteľnosti boolovskej formuly je v $NP$. Daná je množina boolovských disjunkcií (klauzúl) $C_1,\dots,C_m$ obsahujúcich litery $\alpha_1,\dots,\alpha_n$, kde $\alpha_i$, $i\in \{1,\dots,n\}$ sú premenné $x_1,\dots,x_n$ alebo ich negácie $\overline x_1,\dots,\overline x_n$. Existuje postupnosť boolovských hodnôt z $\{0,1\}^n$ taká, že po ich priradení premenným $x_1,\dots,x_n$ je konjunkcia \[C_1(\alpha_1,\dots,\alpha_n)\wedge \dots\wedge C_m(\alpha_1,\dots,\alpha_n)=1?\]
Riešenie:
1. Vhodným overením by bolo priradenie, reprezentované ako vektor z $\{0,1\}^n$. Algoritmus overenia by sa jednoducho presvedčil, či $C_i$ sú klauzuly obsahujúce $n$ litier, a že všetky klauzuly sú pravdivé pre správne priradenie overenia.
Zobraziť riešenie Skryť riešenie

Zdroje

Papadimitriou, Ch. - Steiglitz, K.: Combinatorial Optimization - Algorithms and Complexity.
Plesník, J.: Grafové algoritmy, Veda VSAV Bratislava, 1983
Učebný text (S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani)

Doplňujúce úlohy

Úloha: Zostrojte $O(n^2)$ algoritmus na riešenie špeciálneho prípadu splniteľnosti boolovskej formuly: Každá klauzula obsahuje dve litery (2-splniteľnosť). Návod: Nech $F$ je formula obsahujúca dve litery v každej klauzule. Z $F$ konštruujeme orientovaný graf $D(F)=(X,A)$, kde $X$ je množina premenných a ich negácií, ktoré sa vyskytujú v $F$ a $(\lambda_1,\lambda_2)\in A$ je hrana práve vtedy, ak klauzula $(\overline\lambda_1\vee\lambda_2)$ je z $F$. (a) Digraf $D=(V,A)$ je silne súvislý ak, pre každé $u,v\in V$ existuje cesta z $u$ do $v$ a z $v$ do $u$. Navrhnite $O(|A|)$ algoritmus, ktorý o danom digrafe rozhodne, či je silne súvislý. (b) Zostrojte $O(|A|)$ algoritmus, ktorý nájde všetky silne súvislé komponenty digrafu $D=(V,A)$. (c) Dokážte, že ak pre nejakú premennú $x$ platí, že $x$ a $\overline x$ sú v rovnakom silnom komponente $D(F)$, potom $F$ je nesplniteľná. (d) Dokážte opačné tvrdenie k (c).

Úloha: Zostrojte $O(|E|)$ algoritmus, ktorý rozhodne, či graf $G=(V,E)$ je bipartitný.

Úloha: Problém farbenia grafu. Je daný graf $G=(V,E)$ a prirodzené číslo $k$. Existuje zobrazenie $\chi :V\to\{1,2,\dots,k\}$ také, že $(u,v)\in E \Rightarrow \chi(u)\neq\chi(v)$? Dokážte, že problém farbenia grafu je v $NP$ a popíšte detaily certifikátu a kontrolného algoritmu.

Úloha: Popíšte konštrukciu kontrolného algoritmu, ktorý akceptuje reťazec tvaru \[\underbrace{0...0}_{2n}\underbrace{1...1}_{n}\ \ pre \ \ n\geq 1\] pomocou inštrukcií \[l\ \ {\bf if}\ \ \sigma\ \ {\bf then}\ \ (\sigma',o,l).\]

Úloha: Dokážte, že problém rozdelenia množiny prirodzených čísel \[\{a_1,\dots,a_n\}\] na dve podmnožiny s rovnakým súčtom je NP-úplný aj v prípade ak $a_i\neq a_j,\ i\neq j.$ Návod: Rozdeľte množinu \[\{1,2,...,n,Ka_1+1,Ka_2+2,...,Ka_n+n\}\] pre dostatočne veľké $K$.

Úloha: Dokážte: Ak by sme mali polynomiálny algoritmus na výpočet dĺžky najkratšej TSP cesty, potom by sme mali polynomiálny algoritmus na nájdenie najkratšej TSP cesty.

Úloha: Dokážte, že ILP je v $NP$.

Úloha: Uvažujme o probléme nájdenia najkratšej $s,t)$cesty v ohodnotenom digrafe, keď pripušťame existenciu záporných ohodnotení. (a) Dokážte, že existuje polynomiálny algoritmus pre tento problém ak predpokladáme, že neexistuje záporný cyklus. (b) Dokážte, že bez predpokladu neexistencie záporného cyklu je tento problém ťažko riešiteľný. Daný je graf $G=(V,E)$, množina $L\subset V$ a prirodzené číslo $k$. Dokážte, že problém je NP-úplný Existuje v $G$ kostra grafu $T$ taká, že množina koncových vrcholov kostry $T$ je $L$?\\

Úloha: Dokážte, že nasledujúci problém je NP-úplný Daný je digraf $D=(V,A)$ a $2k$ vrcholov $s_1,s_2,\dots,s_k,t_1,t_2,\dots,t_k\in V$. Existuje v $D$ $k$ vrcholovo-disjunktných ciest z \[s_1\ \ do \ \ t_1,\ \ s_2\ \ do\ \ t_2,\ ...,\ s_k\ \ do\ \ t_k?\]

Úloha: Navrhnite algoritmus na testovanie, či daný graf obsahuje záporný cyklus.