Крышка Vertex - Vertex cover

Пример графа, у которого есть вершинное покрытие, состоящее из 2 вершин (внизу), но ни одна из них не имеет меньшего числа.

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

Задача о минимальном покрытии вершин может быть сформулирована как полуцелая линейная программа , двойственная линейная программа которой является задачей максимального согласования .

Проблемы вершинного покрытия были обобщены на гиперграфы , см. Вершинное покрытие в гиперграфах .

Определение

Примеры вершинных покрытий

Примеры минимальных покрытий вершин

Формально вершина крышки неориентированного графа является подмножеством таким образом, что , то есть , чтобы сказать , что это множество вершин , где каждое ребро имеет , по меньшей мере , одну конечную точку в крышке вершины . Говорят, что такой набор покрывает края . На верхнем рисунке показаны два примера покрытий вершин, при этом некоторые покрытия вершин отмечены красным. ${\ displaystyle V '}$${\ Displaystyle G = (V, E)}$${\ displaystyle V}$${\ displaystyle uv \ in E \ Rightarrow u \ in V '\ lor v \ in V'}$${\ displaystyle V '}$${\ displaystyle V '}$${\ displaystyle G}$${\ displaystyle V '}$

Минимальная вершина крышка является вершиной крышка наименьшего возможного размера. Число вершин покрытия является размером минимальной вершины крышки, то есть . На нижнем рисунке показаны примеры минимальных покрытий вершин на предыдущих графиках. ${\ Displaystyle \ тау}$${\ Displaystyle \ тау = | V '|}$

Примеры

• Множество всех вершин - это вершинное покрытие.
• Концы любого максимального паросочетания образуют вершинное покрытие.
• Полный двудольный граф имеет минимальную вершину крышку размера .${\ displaystyle K_ {m, n}}$${\ Displaystyle \ тау (К_ {м, п}) = \ мин \ {\, м, п \, \}}$

Характеристики

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

Вычислительная проблема

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

ЭКЗЕМПЛЯР: График ${\ displaystyle G}$

ВЫХОД: Наименьшее число , имеющее размер вершинного покрытия .${\ displaystyle k}$${\ displaystyle G}$${\ displaystyle k}$

Если проблема сформулирована как проблема решения , она называется проблемой вершинного покрытия :

ЭКЗЕМПЛЯР: График и положительное целое число .${\ displaystyle G}$${\ displaystyle k}$

ВОПРОС: Имеет ли вершинное покрытие максимального размера ?${\ displaystyle G}$${\ displaystyle k}$

Проблема вершинного покрытия является NP-полной проблемой: это была одна из 21 NP-полных проблем Карпа . Он часто используется в теории сложности вычислений в качестве отправной точки для доказательств NP- сложности .

Формулировка ПДОДИ

Предположим, что с каждой вершиной связана стоимость . Задача (взвешенного) минимального вершинного покрытия может быть сформулирована как следующая целочисленная линейная программа (ЦЛП). ${\ Displaystyle с (v) \ geq 0}$

минимизировать	${\ displaystyle \ textstyle \ sum _ {v \ in V} c (v) x_ {v}}$			(минимизировать общую стоимость)
при условии	${\ Displaystyle х_ {и} + х_ {v} \ geq 1}$	для всех ${\ Displaystyle \ {и, v \} \ в E}$		(покрыть каждое ребро графа),
	${\ displaystyle x_ {v} \ in \ {0,1 \}}$	для всех . ${\ displaystyle v \ in V}$		(каждая вершина либо находится в вершинном покрытии, либо нет)

Этот ILP принадлежит к более общему классу ILP для покрытия проблем . Целочисленность Разрыв этого ILP является , поэтому его релаксации (позволяя каждой переменной , чтобы быть в интервале от 0 до 1, а не требует переменных , чтобы быть только 0 или 1) дает фактор- алгоритм аппроксимации для задачи минимального вершинного покрова. Кроме того, линейное программирование релаксации этого ILP является полуцелым , то есть существует оптимальное решение, для которого каждый элемент равен 0, 1/2 или 1. Из этого дробного решения можно получить 2-приближенное покрытие вершин. путем выбора подмножества вершин, переменные которых не равны нулю. ${\ displaystyle 2}$${\ displaystyle 2}$ ${\ displaystyle x_ {v}}$

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

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

Для двудольных графов эквивалентность между вершинным покрытием и максимальным согласованием, описываемая теоремой Кёнига, позволяет решить проблему двудольного вершинного покрытия за полиномиальное время .

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

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

Исчерпывающий поиск алгоритм может решить проблему во время- ^к п ^{O (1)} , где K является размером крышки вершины. Таким образом, вершинное покрытие является управляемым с фиксированным параметром , и если нас интересуют только малые k , мы можем решить проблему за полиномиальное время . Один из работающих здесь алгоритмов называется алгоритмом ограниченного дерева поиска , и его идея состоит в том, чтобы многократно выбирать некоторую вершину и рекурсивно ветвиться, с двумя случаями на каждом шаге: поместить либо текущую вершину, либо всех ее соседей в вершинное покрытие. Алгоритм решения вершинного покрытия, достигающий наилучшей асимптотической зависимости от параметра, выполняется во времени . Значение клама этой временной границы (оценка наибольшего значения параметра, которое может быть решено за разумный промежуток времени) составляет приблизительно 190. То есть, если не могут быть найдены дополнительные алгоритмические улучшения, этот алгоритм подходит только для случаев, вершина которых номер на обложке 190 или меньше. При разумных предположениях теории сложности, а именно гипотезе экспоненциального времени , время работы не может быть улучшено до 2 ^{o ( k )} , даже если оно равно . ${\ Displaystyle О (1,2738 ^ {k} + (к \ cdot п))}$${\ displaystyle n}$${\ Displaystyle О (к)}$

Однако для плоских графов и в более общем плане для графов, исключающих некоторый фиксированный граф в качестве второстепенного, вершинное покрытие размера k может быть найдено во времени , т. Е. Проблема субэкспоненциально разрешима с фиксированным параметром . Этот алгоритм снова является оптимальным в том смысле, что согласно гипотезе экспоненциального времени ни один алгоритм не может решить вершинное покрытие на плоских графах за время . ${\ Displaystyle 2 ^ {О ({\ sqrt {k}})} п ^ {О (1)}}$${\ Displaystyle 2 ^ {о ({\ sqrt {k}})} п ^ {О (1)}}$

Примерная оценка

Можно найти приближение с множителем 2 , многократно вводя оба конца ребра в вершинное покрытие, а затем удаляя их из графа. Помещенный иначе, мы находим максимальное паросочетание М с жадным алгоритмом и построить сопроводительную вершину C , которая состоит из всех концов ребер в М . На следующем рисунке максимальное соответствие M отмечено красным, а вершинное покрытие C отмечено синим.

Построенное таким образом множество C является вершинным покрытием: предположим, что ребро e не покрыто C ; тогда M  ∪ { e } - паросочетание и e  ∉  M , что противоречит предположению о максимальности M. Более того, если e  = { u ,  v } ∈ M , то любое вершинное покрытие, включая оптимальное вершинное покрытие, должно содержать u или v (или оба); в противном случае ребро e не покрывается. То есть оптимальное покрытие содержит по крайней мере одну конечную точку каждого ребра в M ; в сумме множество C не более чем в 2 раза больше оптимального покрытия вершин.

Этот простой алгоритм был независимо открыт Фаникой Гаврил и Михалисом Яннакакисом .

Более сложные методы показывают, что существуют алгоритмы аппроксимации с немного лучшим коэффициентом аппроксимации. Например, известен алгоритм аппроксимации с коэффициентом приближения . Проблема может быть аппроксимирована коэффициентом аппроксимации в плотных графах. ${\ Displaystyle 2- \ Theta \ left (1 / {\ sqrt {\ log | V |}} \ right)}$${\ displaystyle 2 / (1+ \ delta)}$${\ displaystyle \ delta}$

Неприблизимость

Нет лучшего алгоритма аппроксимации с постоянным коэффициентом, чем описанный выше. Задача о минимальном покрытии вершин является APX-полной , то есть ее нельзя сколь угодно хорошо аппроксимировать, если P  =  NP . Используя методы теоремы PCP , Динур и Сафра доказали в 2005 году, что минимальное вершинное покрытие не может быть аппроксимировано с коэффициентом 1,3606 для любой достаточно большой степени вершины, если только P  =  NP . Позже коэффициент был улучшен до любого . Более того, если гипотеза об уникальных играх верна, то минимальное покрытие вершин не может быть аппроксимировано каким-либо постоянным множителем лучше 2. ${\ displaystyle {\ sqrt {2}} - \ epsilon}$${\ displaystyle \ epsilon> 0}$

Хотя нахождение вершинного покрытия минимального размера эквивалентно нахождению независимого множества максимального размера, как описано выше, две проблемы не эквивалентны с точки зрения сохранения аппроксимации: проблема независимого множества не имеет аппроксимации с постоянным коэффициентом, если только P  =  NP .

Псевдокод

APPROXIMATION-VERTEX-COVER(G)=
C = ∅
E'= G.E

while E' ≠ ∅:
    let (u, v) be an arbitrary edge of E'
    C = C ∪ {u, v}
    remove from E' every edge incident on either u or v

return C

Приложения

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

Заметки

Рекомендации

Внешние ссылки

• Вайсштейн, Эрик В. "Vertex Cover" . MathWorld .
• Вайсштейн, Эрик В. «Минимальное вершинное покрытие» . MathWorld .
• Вайсштейн, Эрик В. "Номер вершинного покрытия" . MathWorld .
• Переходы через реки (и номера Алкуина) - Numberphile