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 . Čí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ů , ž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
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ů 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 , tak zbydou uzly nezávislé podmnožiny velikosti k.
Převod proto lze vyjádřit jako
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.