Вершинное покрытие
-
Определение и свойства вершинного покрытия
- Вершинное покрытие – это подмножество вершин графа, которое покрывает все ребра.
- Минимальное вершинное покрытие – это вершинное покрытие с наименьшим числом вершин.
- Максимальное вершинное покрытие – это вершинное покрытие, содержащее все вершины графа.
-
NP-полнота задачи о минимальном вершинном покрытии
- Задача о минимальном вершинном покрытии является NP-полной, что означает, что не существует эффективного алгоритма для ее точного решения.
- Карп использовал задачу о минимальном вершинном покрытии для доказательства NP-полноты других задач.
-
Вычислительная сложность задачи о минимальном вершинном покрытии
- Задача может быть сформулирована как целочисленная линейная программа (ILP), что позволяет использовать методы оптимизации.
- Существуют алгоритмы аппроксимации с различными коэффициентами, но не известно постоянного коэффициента лучше 2.
-
Управляемость с фиксированными параметрами
- Существуют алгоритмы, которые решают задачу за полиномиальное время для фиксированного значения параметра k.
- Для плоских графов задача может быть решена за время, пропорциональное
- 2
- O
- (
- k
- )
- n
- 1
- {\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}
- .
-
Приближенная оценка и недостижимость
- Можно найти приближение с коэффициентом 2, удаляя конечные точки ребер из покрытия вершин.
- Задача о минимальном вершинном покрытии является APX-полной, что означает невозможность аппроксимации лучше, чем 2, если P = NP.
Полный текст статьи: