IB102 – úkol 11, příklad 1 – řešení Odevzdání: 15. 12. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém rozhodnout, zda v daném orientovaném grafu existují
alespoň 2 různé hamiltonovské cesty z vrcholu s do vrcholu t (lišící se alespoň jednou
hranou), je NP-těžký. Jinak řečeno, dokažte, že jazyk 2-HAMPATH definovaný níže zadává
NP-těžký problém.
2-HAMPATH = { G, s, t | G je orientovaný graf obsahující alespoň 2 různé
hamiltonovské cesty z s do t}
V důkazu můžete využít faktu, že problém hamiltonovské cesty (definovaný níže) je
NP-úplný:
HAMPATH = { G, s, t | G je orientovaný graf obsahující hamiltonovskou cestu z s do t}.
Bonus [1 bod] Dokažte, že problém 2-HAMPATH je dokonce NP-úplný. Tedy dokažte
navíc, že 2-HAMPATH ∈ NP.
Bonus [1 bod] Dokažte, že jazyk k-HAMPATH definovaný níže je NP-úplný pro libovolné
k ≥ 1:
k-HAMPATH = { G, s, t | G je orientovaný graf obsahující alespoň k různých
hamiltonovských cest z s do t}
Abychom ukázali, že problém 2-HAMPATH je NP-těžký, musíme dokázat, že všechny
problémy ze složitostní třídy NP je možné na něj polynomiálně redukovat. Využijeme
přitom faktu, že problém HAMPATH je NP-těžký, a najdeme redukci
HAMPATH ≤p 2-HAMPATH.
Potřebujeme tedy najít funkci f, totálně vyčíslitelnou v polynomiálním čase takovou, že
w ∈ HAMPATH ⇔ f(w) ∈ 2-HAMPATH
Intuice: Funkce f musí mít tu vlastnost, že kdybychom měli k dispozici TS rozhodující
problém 2-HAMPATH a někdo by se nás zeptal, jestli graf G obsahuje hamiltonovskou
cestu z s do t, my budeme umět vstup w = G, s, t přetransformovat funkcí f a následně
na vstupu f(w) = G , s , t spustit náš TS, který dotaz zodpoví. Musí platit, že když náš
TS akceptuje (G obsahuje alespoň 2 hamiltonovské cesty z s do t ), tak původní graf G
obsahoval hamiltonovskou cestu z s do t. Když náš stroj zamítne, původní graf G žádnou
hamiltonovskou cestu neobsahoval.
Nechť tedy HAMPATH ⊆ Σ∗
a 2-HAMPATH ⊆ Φ∗
. Funkce f : Σ∗
→ Φ∗
je definována
následovně:
f(w) =
Ge, s , t , jestliže w není kódem žádné trojice popisující graf a jeho dva vrcholy,
G , s , t , jestliže w = G, s, t pro nějaký graf G a jeho dva vrcholy s, t
IB102 – úkol 11, příklad 1 – řešení Odevzdání: 15. 12. 2014
Vypracoval(a): UČO:
Skupina:
Kde Ge popisuje graf s vrcholy s a t neobsahující žádnou hranu. Zkontrolovat tvar vstupního
slova jistě zvládneme v polynomiálním čase a zapsat na výstup kód Ge, s , t nám
zabere konstantní čas.
Graf G vznikne z grafu G tak, že zvolíme libovolný vrchol v grafu G a „rozdělíme“ jej na
čtyři vrcholy v1, v2, v3, v4. Do vrcholu v1 povedou všechny hrany, které vedly do původního
vrcholu v. Obdobně z vrcholu v4 povedou všechny hrany, které předtím vedly z vrcholu v.
Dále přidáme hrany v1 → v2, v1 → v3, v2 → v4, v3 → v4, v2 → v3, v3 → v2. Jestliže v = s,
s := s, obdobně pro t. Jestliže v = s, pak s := v1, resp. jestliže v = t, pak t := v4.
v1
v2
v3
v4
Tuto modifikaci lze provést v polynomiálním (pro rozumné kódování grafu v lineárním)
čase, tedy celkově platí, že funkce f má polynomiální složitost a je i totálně vyčíslitelná.
Zbývá ještě dokázat, že platí:
w ∈ HAMPATH ⇔ f(w) ∈ 2-HAMPATH
„⇒“: Předpokládejme, že w = G, s, t ∈ HAMPATH. G tedy obsahuje hamiltonovskou
cestu z s do t. V našem modifikovaném grafu G jsou úseky cesty z vrcholu s po vrchol
v1 a z v4 po vrchol t stejné jako hamiltonovská cesta mezi vrcholy s, v a vrcholy v, t
v původním grafu. Úsek cesty mezi vrcholy v1 a v4 však možno projít dvěma různými
způsoby. Můžeme nejdříve navštívit vrchol v2 nebo vrchol v3 a v obou cestách pokrýt
všechny vrcholy grafu G . Nutně tedy platí, že graf G obsahuje alespoň dvě hamiltonovské
cesty z s do t :
s → ... → v1 → v2 → v3 → v4 → ... → t ,
s → ... → v1 → v3 → v2 → v4 → ... → t
Tedy jistě platí: f(w) = G , s , t ∈ 2-HAMPATH.
„⇐“: Dokážeme obměnu implikace, tedy: w /∈ HAMPATH ⇒ f(w) /∈ 2-HAMPATH
Mohou nastat dva případy, proč w /∈ HAMPATH:
1. w nepopisuje trojici G, s, t , kde G je graf a s, t ∈ G. Pak ale f(w) = Ge, s , t
určitě nemůže obsahovat dvě hamiltonovské cesty, protože vrcholy s a t mezi sebou
nemají žádnou hranu.
2. w = G, s, t , ale mezi vrcholy s a t není hamiltonovská cesta. Popsanou transformací
grafu však nemůže vzniknout ani jedna hamiltonovská cesta, natož dvě, protože
modifikujeme jenom jeden vrchol a nepřidáváme tak žádné hrany mezi původními
vrcholy grafu.
IB102 – úkol 11, příklad 1 – řešení Odevzdání: 15. 12. 2014
Vypracoval(a): UČO:
Skupina:
Dokázali jsme tedy, že problém HAMPATH umíme zredukovat na problém 2-HAMPATH,
z čehož plyne, že 2-HAMPATH je NP-těžký.
Bonus [1 bod] Abychom dokázali, že problém 2-HAMPATH je NP-úplný, musíme
ukázat, že 2-HAMPATH ∈ NP. Podobně jako v důkazu příslušnosti HAMPATH do třídy
NP, i tady můžeme argumentovat tím, že obě cesty lze uhodnout v polynomiálním počtu
kroků. V polynomiálním počtu kroku lze také zkontrolovat, že tyto dvě cesty jsou různé,
tedy ověřit, že se liší alespoň v jedné hraně. Problém 2-HAMPATH tedy náleží do třídy
NP a jelikož na něj umíme redukovat všechny problémy třídy NP, je také NP-úplný.
Bonus [1 bod] Důkaz, že jazyk k-HAMPATH je NP-těžký je velice podobný jako
pro problém 2-HAMPATH. Místo transformace libovolného vrcholu v na čtyři jej však
nahradíme k + 2 vrcholy. Modifikace vypadá následovně:
vin
v1
v2
v3
...
vk
vout
Jestli původní graf G obsahoval hamiltonovskou cestu, graf G bude obsahovat nejméně
k hamiltonovských cest. Část cesty z s po vin, resp. z vout po t , je stejná jako cesta v
původním grafu z s do v, resp. z v do t. k různých cest mezi vrcholy vin a vout o délce
k + 2 vypadá následovně:
vin → vi → vi+1 → ... → vk → v1 → ... → vi−1 → vout
V případě, že původní graf G žádnou hamiltonovsku cestu mezi vrcholy s a t neobsahoval,
modifikací žádná nová hamiltonovská cesta mezi vrcholy s a t v grafu G vzniknout
nemohla (stejně jako u 2-HAMPATH ), tedy G , s , t /∈ k-HAMPATH.
Příslušnost do třídy NP je také zřejmá – uhodneme k hamiltonovských cest z s do t a
následně ověříme, že žádné dvě cesty nejsou stejné. Vše zvládneme v polynomiálním počtu
kroku vzhledem k velikosti grafu G. Problém k-HAMPATH je tedy i NP-úplný.