Вариант минимального покрытия вершин

Question

В своем исследовании я сталкиваюсь с одним из вариантов проблемы покрытия вершин следующим образом:

Учитывая граф G, вершину v и число k, чтобы решить, имеет ли G покрытие вершины размера k, которое содержит v.

Я искал всю литературу и не смог найти подобную проблему. Меня интересует сложность этой проблемы (я доказал, что она завершена для $P^NP[long]$).

Вопрос в том, видели ли вы когда-нибудь такой вариант проблемы покрытия вершин? Как вы называете эту проблему?

Answer 1

Даны граф G и целое число K, чтобы решить, имеет ли G покрытие вершины размера K является решением задачи о минимальном покрытии вершин. И это NP-полный.

На самом деле, проблема, которую вы описали, не отличается от этой. Это потому, что если вы содержали вершину v, вы можете удалить v и все ребра, имеющие v в качестве конечной точки. Что вы должны сделать дальше, это решить, можете ли вы покрыть левый подграф k-1 Вершины.