Problém s pokrytím kliknutí

Problém pokrytí kliky je výpočetní problém, který spočívá v určení možnosti rozdělení vrcholů grafu na kliky . Je NP-úplný ; je zařazen do seznamu 21 NP-úplných Karpových problémů [1] . $k$

Vzhledem k rozdělení vrcholů do množin je možné v polynomiálním čase určit , že každá množina tvoří kliku, takže problém patří do třídy NP . NP-úplnost problému krytu kliky vyplývá z jeho redukce na problém zbarvení grafu : rozklad grafu na kliku odpovídá nalezení rozkladu vrcholů doplňku na nezávislé množiny (každé z těchto množin lze přiřadit jednu barvu, což dává a - zbarvení). $k$ $G$ $k$ $G'$ $k$ $k$

Minimální velikost obálky kliknutí v grafu je nejmenší číslo , pro které existuje obálka kliknutí. $k$

Související problém nalezení průsečíku uvažuje množiny klik, které zahrnují všechny hrany daného grafu; tento problém je také NP-úplný.

Poznámky

↑ Karp, 1975 , str. 16-38.

Literatura

Richard Karp. Proceedings of a Symposium on the Complexity of Computer Computations / RE Miller, JW Thatcher. - Plénum Press, 1972. - S. 85-103.
- PM Karp. Kybernetická sbírka (nová řada) / O. B. Lupanov. - M .: "Mir", 1975. - S. 16-38.
Michael R. Garey, David S. Johnson. Počítače a neovladatelnost: Průvodce teorií NP-úplnosti . - W.H. Freeman, 1979. - ISBN 0-7167-1045-5 . A1.2: GT19, strana 194.
- Gary M., Johnson D. Výpočetní stroje a obtížné úkoly. - M. , 1982.