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

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

Определение

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

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

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

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

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

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

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

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

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

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

NP-полнота

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

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

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

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

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

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

Ссылки

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