Problémy klik a nezávislých množin jsou NP-úplné grafové úlohy. Pokud bychom pouze věděli, že je problém klik NP-úplný, ale o nezávislých množinách tuto informaci neměli, tak tento převod dokazuje NP-úplnost úlohy nezávislých množin (ukázat, že lze zkontrolovat ANO-instanci v polynomiálním čase, je triviální - stačí projít sousedy uzlů z nezávislé množiny N a testovat jejich nepřítomnost v N).
Nezávislé podmnožiny
Podmnožina uzlů grafu G je nezávislá právě tehdy, když žádné dva z jejích uzlů neincidují s 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.
Klikovost grafu
Klika grafu je každý maximální úplný podgraf grafu G (tj. každý úplný podgraf pro který platí, že žádný z jeho nadgrafů není úplný). Maximální číslo k, pro které existuje v G klika o k vrcholech nazýváme klikovostí grafu.
Rozhodovací problém klikovosti grafu se ptá, zda-li v daném grafu existuje klika alespoň o k vrcholech.
Převod
Z definice klik plyne, že se jedná o ty uzly, které jsou vzájemně propojeny hranami. Nezávislá množina naopak požaduje, aby tyto uzly nebyly projeny vůbec. Pro převod proto stačí ke grafu G vytvořit opačný graf .
Protože lze k zadanému grafu vytvořit opačný graf v polynomiálním čase, tak je tento převod polynomiální.
Literatura
- DEMLOVÁ, Marie. Teorie algoritmů : Text k přednášce.