Nezávislé množiny → Vrcholové pokrytí

Problém nezávislých množin a problém vrcholového pokrytí jsou dvě NP-úplné grafové úlohy. Pokud bychom pouze věděli, že jsou nezávislé množiny NP-úplné, ale o vrcholovém pokrytí tuto znalost neměli, tak tento převod dokazuje právě NP-úplnost problému vrcholového pokrytí (ještě je třeba ukázat, že je problém vrcholového pokrytí v NP, ověření ANO-instance lze udělat například značkovacím algoritmem v polynomiálním čase).

Nezávislé množiny

Podmnožina uzlů grafu G je nezávislá právě tehdy, když žádné dva z jejích uzlů neincidují se stejnou hranou E \\in Edges(G). Číslo, které označuje počet uzlů maximální nezávislé podmnožiny nazýváme nezávislostí grafu.

Rozhodovací problém nezávislých podmnožin se ptá, zda-li v daném grafu existuje nezávislá podmnožina alespoň o k vrcholech.

Vrcholové pokrytí

Vrcholové pokrytí (dominující podmnožina grafu) je taková podmnožina uzlů D \\subseteq G, že každá hrana grafu má alespoň jeden krajní uzel v D. Počet uzlů minimální dominující podmnožiny nazýváme dominancí grafu.

Rozhodovací problém vrcholového pokrytí se ptá, zda-li v daném grafu existuje vrcholové pokrytí maximálně o k vrcholech.

Převod

Nezávislé množiny a vrcholové pokrytí
Nezávislé množiny (zeleně) a vrcholové pokrytí (oranžově)

Z definice nezávislých podmnožin plyne, že nezávislá množina N obsahuje ty vrcholy, mezi nimiž nejsou žádné hrany. V množině vrcholů G \\setminus N tedy zbudou uzly, se kterými incidují jak hrany vedoucí z uzlů z N, tak všechny ostatní hrany (protože jiné uzly nebyly odebrány). Jinými slovy zbudou uzly vrcholového pokrytím grafu G.

Z opačné strany je zřejmé, že pokud odebereme uzly vrcholového pokrytí velikosti n - k, tak zbydou uzly nezávislé podmnožiny velikosti k.

Převod proto lze vyjádřit jako

G \\rightarrow G
k \\rightarrow n - k
n - počet uzlů grafu G
N - vrcholové pokrytí grafu G

Protože dochází pouze k úpravě čísla k, tak je převod polynomiální.

Literatura

  • DEMLOVÁ, Marie. Teorie algoritmů : Text k přednášce.







Doporučujeme