Deterministi c решений для задач минимального покрытия вершин - NP Complete в порядке

Question

Задача о вершинном покрытии состоит в том, чтобы найти множество ψ для неориентированного графа G = (V, E) для ψ ∈ V, такого, что если {u, v} ∈ E, то либо u ∈ ψ, либо v ∈ ψ, либо и то, и другое. Эта проблема определена и доказана как NP-полная.

Существуют ли детерминированные c алгоритмы, которые могут решить эту проблему? Экспоненциальное время работы приемлемо, но есть ли лучшие детерминированные алгоритмы c? Я нашел похожий вопрос и только один подход Использование двоичного поиска . Я не ищу приблизительных решений, которые можно было бы запустить за меньшее время - насколько я понимаю, тот, который перечислен в главе 35 текста Кормена, Лейзерсона, Ривеста и Штейна (CLRS), является приближенным алгоритмом.

Answer 1

Вы можете использовать дерево поиска для этой проблемы. Для каждого ребра {v, w} есть 3 варианта.

1. v включено
2. w включено
3. включены оба.

Вы также можете применить некоторые правила отсечения, например следующие:

1. Если вершина v имеет степень 1, включить соседа v в V C.
2. Если для двух соседей v и w набор соседей v является подмножеством соседей w, включите w в V C.

Оба эти правила могут быть доказаны в почувствуйте, что выбор, который вы делаете в соответствии с этими правилами, по крайней мере так же хорош, как и любой другой выбор, который вы могли бы сделать для рассматриваемого преимущества.