NP-полнота задачи о вершинном покрытии

Определение

Вершинным покрытием графа [math]G[/math] называется такое множество [math]V[/math] его вершин, что у любого ребра в [math]G[/math] хотя бы одна из вершин лежит в [math]V[/math]. Размер вершинного покрытия - это число входящих в него вершин.

Формулировка

Языком COVER называется множество пар [math]\langle G,k \rangle[/math], где [math]G[/math] - неориентированный граф, [math]k[/math] - натуральное число. Слово принадлежит языку COVER, если ли граф [math]G[/math] содержит вершинное покрытие размера [math]k[/math]. Задача о вершинном покрытии является NP-полной.

Доказательство NP-полноты

Для доказательства NP-полноты задачи о вершинном покрытии покажем, что она является NP-трудной и принадлежит классу NP.

Задача о вершинном покрытии является NP-трудной

Для доказательства сведем по Карпу задачу о независимом множестве к нашей.

[math]IND \le_{k} COVER[/math]

Докажем сначала, что вершинное покрытие и независимое множество являются дополнениями друг друга. Пусть в графе [math]G[/math] выбрано независимое множество вершин [math]V[/math]. Тогда у любого ребра из [math]G[/math] одна из вершин не лежит в [math]V[/math], так как иначе какие-то две вершины в [math]V[/math] были бы соединены ребром. Значит дополнение [math]V[/math] - вершинное покрытие. Пусть теперь в графе [math]G[/math] выбрано вершинное покрытие [math]V[/math]. Любому ребру в [math]G[/math] инциндентна хотя бы одна вершина из [math]V[/math], значит никакое ребро не может соединять две вершины из дополнения [math]V[/math], поэтому дополнение [math]V[/math] - независимое множество.

Пусть в графе [math]G[/math] c [math]n[/math] вершинами необходимо найти независимое множество размера [math]k[/math]. По доказанному выше оно существует тогда и только тогда, когда в [math]G[/math] есть вершинное покрытие размера [math]n-k[/math]. Данное сведение можно выполнить за полиномиальное время

Задача о вершинном покрытии принадлежит классу NP

В качестве сертификата возьмем набор из [math]k[/math] вершин. Если в графе [math]e[/math] ребер, то за время [math]O(ek)[/math] можно проверить, что для каждого ребра одна из инциндентных ему вершин лежит в данном наборе.