Независимое множество в графе

Question

Как вы знаете, нахождение максимального независимого набора - это NP. Есть ли алгоритм, чтобы узнать, имеет ли данный граф Независимый набор по крайней мере k вершин? Обратите внимание, что мы не хотим его найти. Мы просто хотим выяснить, существует ли такая вещь.

Answer 1

Цитирование Википедия :

В задаче решения с независимым набором входные данные представляют собой неориентированный граф и число k , а выходные данные представляют собой логическое значение: true, если граф содержит независимый набор размера k и ложь в противном случае.

Эта проблема является NP-полной. Ваша задача задает тот же вопрос, просто по-другому сформулированный, потому что граф имеет независимый набор по крайней мере k вершин, если и только если он имеет независимый набор точно k вершин. 1017 *

Это означает, что ваша проблема тоже NP-завершена.