Это NP завершено?

Question

Решение проблемы: для заданного графа G и чисел "a", "b" необходимо ответить, существует ли набор вершин "a", совокупная окрестность которых имеет размер, по крайней мере, "b". Как мы покажем, что эта проблема NPC?

Answer 1

Я думаю, что если бы вы могли решить эту проблему за полиномиальное время, вы могли бы решить https://en.wikipedia.org/wiki/Maximum_cut за полиномиальное время. Согласно статье, решение проблемы в Max-Cut гласит: "Учитывая граф G и целое число k, определите, есть ли сечение размера по крайней мере k в G".

Учитывая что-то, что решает вашу a/b версию проблемы, я бы решил версию Max-Cut, установив b=k и попробовав a=1,2,3..size графа, который все равно будет иметь полиномиальную стоимость в размере ввода, (или, возможно, b=k + a в зависимости от того, что вы подразумеваете под размером соседства).

(Так что да, я думаю, что ваша проблема является NP-полной).