Введение

Подмножество вершин графа, включающее по крайней мере одну конечную точку каждого ребра.

В теории графов, вершинное покрытие (иногда называемое узловым покрытием) графа — это множество вершин, включающее по крайней мере одну конечную точку каждого ребра графа. В информатике, задача поиска минимального вершинного покрытия является классической задачей оптимизации. Она является NP-трудной, поэтому её нельзя решить алгоритмом за полиномиальное время, если P ≠ NP. Более того, её сложно приближённо решать – её нельзя приблизить с точностью до коэффициента меньше 2, если верна гипотеза об однозначных играх. С другой стороны, существуют несколько простых 2-аппроксимационных алгоритмов. Это типичный пример NP-трудной задачи оптимизации, для которой существует алгоритм приближения. Её задача принятия решения, задача вершинного покрытия, была одной из 21 NP-полных задач Карпа и, следовательно, является классической NP-полной задачей в теории вычислительной сложности. Кроме того, задача вершинного покрытия является фиксированно-параметрически разрешимой и центральной задачей в параметризованной теории сложности. Задача поиска минимального вершинного покрытия может быть сформулирована как полуцелочисленная линейная программа, двойственная линейная программа которой является задачей о максимальном паросочетании. Задачи вершинного покрытия были обобщены на гиперграфы, см. Вершинное покрытие в гиперграфах.

Определение

Формально, вершинное покрытие неориентированного графа — это подмножество вершин, такое что , то есть это множество вершин, где каждая ребро имеет хотя бы одну конечную точку в вершинном покрытии. Такое множество называется покрывающим ребра графа. На верхней иллюстрации показаны два примера вершинных покрытий, при этом некоторые вершинные покрытия выделены красным цветом. Минимальное вершинное покрытие — это вершинное покрытие наименьшего возможного размера. Число вершинного покрытия — это размер минимального вершинного покрытия, то есть. На нижней иллюстрации показаны примеры минимальных вершинных покрытий для предыдущих графов.

Примеры

Множество всех вершин является вершинным покрытием. Конечные точки любого максимального паросочетания образуют вершинное покрытие. Полный двудольный граф имеет минимальное вершинное покрытие размера .

Свойства

Множество вершин является вершинным покрытием тогда и только тогда, когда его дополнение является независимым множеством. Следовательно, число вершин графа равно его числу минимального вершинного покрытия плюс размер максимального независимого множества.

Точная оценка

Вариант задачи о покрытии вершин является NP-полным, что означает, что вряд ли существует эффективный алгоритм для её точного решения для произвольных графов. NP-полноту можно доказать сведением из 3-SAT или, как это сделал Карп, сведением из задачи о клике. Покрытие вершин остаётся NP-полным даже для кубических графов и даже для планарных графов степени не более 3. Для двудольных графов эквивалентность между покрытием вершин и максимальным паросочетанием, описанная теоремой Кёнига, позволяет решить задачу о покрытии вершин двудольного графа за полиномиальное время. Для деревьев алгоритм находит минимальное покрытие вершин за полиномиальное время, находя первый лист в дереве и добавляя его родителя в минимальное покрытие вершин, затем удаляя лист и родителя вместе со всеми связанными рёбрами и повторяя процесс, пока в дереве не останется рёбер.

Упражненность с фиксированными параметрами

Исчерпывающий алгоритм поиска может решить проблему за время 2knO(1), где k – размер вершинного покрытия. Следовательно, задача о вершинном покрытии является фиксированно-параметрически разрешимой, и если нас интересует только малое k, мы можем решить задачу за полиномиальное время. Один из алгоритмических приемов, который здесь работает, называется алгоритмом поиска с ограниченным деревом, и его идея заключается в том, чтобы последовательно выбирать некоторую вершину и рекурсивно ветвиться, рассматривая два случая на каждом шаге: включить либо текущую вершину, либо всех её соседей в вершинное покрытие. Алгоритм решения задачи о вершинном покрытии, достигающий наилучшей асимптотической зависимости от параметра, работает за время. Значение klam этого ограничения по времени (оценка наибольшего значения параметра, которое можно решить за разумное время) составляет примерно 190. То есть, если не удастся найти дополнительные алгоритмические улучшения, этот алгоритм подходит только для экземпляров, число вершинного покрытия которых равно 190 или меньше. При разумных предположениях теории сложности, а именно гипотезе об экспоненциальном времени, время работы нельзя улучшить до 2o(k), даже когда . Однако для планарных графов и, в более общем смысле, для графов, не содержащих некоторый фиксированный граф в качестве минора, вершинное покрытие размера k можно найти за время , то есть задача является субэкспоненциально фиксированно-параметрически разрешимой. Этот алгоритм снова оптимален в том смысле, что, согласно гипотезе об экспоненциальном времени, ни один алгоритм не может решить задачу о вершинном покрытии для планарных графов за время .

Приблизительная оценка

Можно найти приближение с коэффициентом 2, последовательно добавляя обе конечные точки каждого ребра в вершинное покрытие, а затем удаляя их из графа. Иными словами, мы находим максимальное паросочетание M с помощью жадного алгоритма и строим вершинное покрытие C, состоящее из всех конечных точек ребер в M. На следующем рисунке максимальное паросочетание M выделено красным цветом, а вершинное покрытие C – синим. Построенное таким образом множество C является вершинным покрытием: предположим, что ребро e не покрыто C; тогда M ∪ {e} является паросочетанием, а e ∉ M, что противоречит предположению о максимальности M. Более того, если e = {u, v} ∈ M, то любое вершинное покрытие – включая оптимальное – должно содержать u или v (или оба); в противном случае ребро e не будет покрыто. Таким образом, оптимальное покрытие содержит хотя бы одну конечную точку каждого ребра в M; следовательно, множество C не более чем в два раза больше оптимального вершинного покрытия. Этот простой алгоритм был независимо открыт Фаникой Гаврилой и Михалисом Яннакакисом. Более сложные методы показывают, что существуют алгоритмы приближения с немного лучшим коэффициентом приближения. Например, известен алгоритм приближения с коэффициентом приближения . Для данной задачи можно получить приближение с коэффициентом приближения в плотных графах.

Недоступность

Неизвестен алгоритм аппроксимации с лучшим постоянным множителем, чем описанный выше. Задача о минимальном вершинном покрытии является APX-полной, то есть, если P ≠ NP, её нельзя аппроксимировать сколь угодно точно. Используя методы, основанные на теореме PCP, Динур и Сафра в 2005 году доказали, что минимальное вершинное покрытие нельзя аппроксимировать с точностью до множителя 1,3606 для графов с достаточно большой степенью вершин, если P ≠ NP. Впоследствии этот множитель был улучшен до … . Более того, если верна гипотеза об уникальных играх, то минимальное вершинное покрытие нельзя аппроксимировать с точностью до любого постоянного множителя, меньшего 2. Хотя нахождение минимального вершинного покрытия эквивалентно нахождению максимального независимого множества, как описано выше, эти две задачи не эквивалентны с точки зрения сохранения аппроксимации: задача об независимом множестве не имеет алгоритма аппроксимации с постоянным множителем, если P ≠ NP.

Приложения

Оптимизация вершинного покрытия служит моделью для множества практических и теоретических задач. Например, коммерческая организация, заинтересованная в установке минимально возможного количества камер видеонаблюдения, охватывающих все коридоры (рёбра), соединяющие все помещения (вершины) на этаже, может сформулировать свою задачу как задачу минимизации вершинного покрытия. Эта задача также использовалась для моделирования удаления повторяющихся последовательностей ДНК в приложениях синтетической биологии и метаболической инженерии.