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

Задача о вершинном покрытии — 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\setminus C$ является независимым множеством, задачи сводятся друг к другу.

NP-полнота

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

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

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

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

Задача о вершинном покрытии в двудольных графах

В двудольных графах задача о вершинном покрытии разрешима за полиномиальное время, поскольку сводится к задаче о наибольшем паросочетании (Теорема Кёнига).

Ссылки

• A compendium of NP optimization problems
• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring

Литература

• Томас Х. Кормен и др. Глава 36. NP-полнота // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 1-е изд. — М.: Московского центра непрерывного математического образования, 2001. — С. 866.