Русская Википедия:Задача о вершинном покрытии
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Определение
Вершинное покрытие для неориентированного графа <math>G = (V, E)</math> — это множество его вершин <math>S</math>, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из <math>S</math>.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Пример: Граф, изображённый справа, имеет вершинное покрытие <math>\{1,3,5,6\}</math> размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как <math>\{2,4,5\}</math> и <math>\{1,2,4\}</math>.
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия графа).
- На входе: Граф <math>G = (V, E)</math>.
- Результат: множество <math>C \sube V </math> — наименьшее вершинного покрытие графа <math>G</math>.
Также вопрос можно ставить как эквивалентную задачу разрешения:
- На входе: Граф <math>G</math> и положительное целое число <math>k</math>.
- Вопрос: Существует ли вершинное покрытие <math>C</math> для графа <math>G</math> размера не более <math>k</math>?
Задача о вершинном покрытии сходна с задачей о независимом множестве. Поскольку множество вершин <math>C</math> является вершинным покрытием тогда и только тогда, когда его дополнение <math> V \setminus C</math> является независимым множеством, задачи сводятся друг к другу.
NP-полнота
Поскольку задача о вершинном покрытии является NP-полной, то, к сожалению, неизвестны алгоритмы для её решения за полиномиальное время. Однако существуют аппроксимационные алгоритмы, дающие «приближённое» решение этой задачи за полиномиальное время — можно найти вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
Один из первых, приходящих в голову, подходов решения задачи - аппроксимация через жадный алгоритм: Необходимо добавлять вершины с максимальным количеством соседей в вершинное покрытие, пока задача не будет решена, однако такое решение не имеет <math>\rho</math>-аппроксимации для любого константного <math>\rho</math>.
Другой вариант решения - нахождение максимального паросочетания <math>M \in E</math> на данном графе <math>G = (V, E)</math> и выбор в качестве вершинного покрытия множества <math>C = \bigcup_{e \in M} e</math>. Корректность такого алгоритма доказывается от противного: Если <math>C</math> не является вершинным покрытием (не обязательно наименьшим), т.е. <math>\exist e \colon e \cap C = \emptyset</math>, то <math>M</math> не является максимальным паросочетанием. Фактор аппроксимации же доказывается следующим образом: Пусть <math>\tau(G) = |V| - \alpha(G)</math>, где <math>\alpha(G)</math> - число независимости графа <math>G</math>, и <math>M_{max}(G)</math> - наибольшее паросочетание графа <math>G</math>. Тогда фактор аппроксимации равен <math>\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>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
Литература
