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

Определение

Вершинное покрытие для неориентированного графа ${\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-полнота

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

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

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

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

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

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

Ссылки

Литература

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