Задача о вершинном покрытии

Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.

Определение

Вершинное покрытие для неориентированного графа $G = (V, E)$ — это множество его вершин $S$ , такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из $S$ .

Размером (size) вершинного покрытия называется число входящих в него вершин.

Пример: Граф, изображённый справа, имеет вершинное покрытие ${1, 3, 5, 6}$ размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как ${2, 4, 5}$ и ${1, 2, 4}$ .

Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия графа).

На входе: Граф

G = (V, E)

.

Результат: множество

C \subseteq V

— наименьшее вершинного покрытие графа

G

.

Также вопрос можно ставить как эквивалентную задачу разрешения:

На входе: Граф

G

и положительное целое число

k

.

Вопрос: Существует ли вершинное покрытие

C

для графа

G

размера не более

k

?

Задача о вершинном покрытии сходна с задачей о независимом множестве. Поскольку множество вершин $C$ является вершинным покрытием тогда и только тогда, когда его дополнение $V ∖ C$ является независимым множеством, задачи сводятся друг к другу.

NP-полнота

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

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

Другой вариант решения - нахождение максимального паросочетания $M \in E$ на данном графе $G = (V, E)$ и выбор в качестве вершинного покрытия множества $C = ⋃_{e \in M} e$ . Корректность такого алгоритма доказывается от противного: Если $C$ не является вершинным покрытием (не обязательно наименьшим), т.е. $\exists e : e \cap C = \emptyset$ , то $M$ не является максимальным паросочетанием. Фактор аппроксимации же доказывается следующим образом: Пусть $τ (G) = | V | - α (G)$ , где $α (G)$ - число независимости графа $G$ , и $M_{m a x} (G)$ - наибольшее паросочетание графа $G$ . Тогда фактор аппроксимации равен $\frac{2 \cdot | M |}{τ (G)} ⩽ \frac{2 \cdot | M_{m a x} (G) |}{τ (G)} ⩽ \frac{2 \cdot | M_{m a x} (G) |}{| M_{m a x} (G) |} = 2$ .

В общем случае задача о вершинном покрытии может быть аппроксимирована с фактором $2 - \frac{\log \log n}{2 \cdot \log n}$ .