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

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

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

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

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

На входе: Граф ${\displaystyle G=(V,E)}$.

Результат: множество ${\displaystyle C\subseteq V}$ — наименьшее вершинного покрытие графа ${\displaystyle G}$.

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

На входе: Граф ${\displaystyle G}$ и положительное целое число ${\displaystyle k}$.

Вопрос: Существует ли вершинное покрытие ${\displaystyle C}$ для графа ${\displaystyle G}$ размера не более ${\displaystyle k}$?

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

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

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

• 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.