Задача о вершинном покрытии
Задача о вершинном покрытии — NP-полная задача информатики в области теории графов. Часто используется в теории сложности для доказательства NP-полноты более сложных задач.
Определение
[править | править код]Вершинное покрытие для неориентированного графа — это множество его вершин , такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из .
Размером (size) вершинного покрытия называется число входящих в него вершин.
Пример: Граф, изображённый справа, имеет вершинное покрытие размера 4. Однако оно не является наименьшим вершинным покрытием, поскольку существуют вершинные покрытия меньшего размера, такие как и .
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия графа).
- На входе: Граф .
- Результат: множество — наименьшее вершинного покрытие графа .
Также вопрос можно ставить как эквивалентную задачу разрешения:
- На входе: Граф и положительное целое число .
- Вопрос: Существует ли вершинное покрытие для графа размера не более ?
Задача о вершинном покрытии сходна с задачей о независимом множестве. Поскольку множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является независимым множеством, задачи сводятся друг к другу.
NP-полнота
[править | править код]Поскольку задача о вершинном покрытии является 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.