Крышка вершины

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

В теории графов покрытие вершин (иногда покрытие узлов ) графа — это набор вершин , который включает хотя бы одну конечную точку каждого ребра графа.

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

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

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

Определение

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

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

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

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

Примеры

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

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

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

Вычислительная задача

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

ПРИМЕР: Граф $G$

ВЫХОД: Наименьшее число $k$ такой, что $G$ имеет вершинное покрытие размера $k$.

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

ПРИМЕР: Граф $G$ и положительное целое число $k$.

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

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

формулировка ILP

Предположим, что каждая вершина имеет связанную с ней стоимость $c(v)\geq 0$. (Взвешенную) задачу минимального вершинного покрытия можно сформулировать как следующую целочисленную линейную программу (ILP).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хотя нахождение вершинного покрытия минимального размера эквивалентно нахождению независимого множества максимального размера, как описано выше, эти две проблемы не эквивалентны с точки зрения сохранения аппроксимации: проблема независимого множества не имеет аппроксимации с постоянным коэффициентом, если только 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

Приложения

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

См. также

• Доминирующий набор

Ссылки

• Чен, Цзянер; Кандж, Ияд А.; Ся, Ге (2006). «Улучшенные параметризованные верхние границы для вершинного покрытия». Математические основы информатики 2006: 31-й международный симпозиум, MFCS 2006, Стара Лесна, Словакия, 28 августа – 1 сентября 2006 г., Материалы (PDF) . Конспекты лекций по информатике. Том. 4162. Шпрингер-Верлаг. стр. 238–249. дои : 10.1007/11821069_21 . ISBN  978-3-540-37791-7 .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стоун, Клиффорд (2001). Введение в алгоритмы . Кембридж, Массачусетс: MIT Press и McGraw-Hill. стр. 1024–1027 . ISBN  0-262-03293-7 .
• Демейн, Эрик ; Фомин Федор Владимирович; Хаджиагайи, Мохаммад Таги; Тиликос, Димитриос М. (2005). «Субэкспоненциальные параметризованные алгоритмы на графах ограниченного рода и графах без H-миноров» . Журнал АКМ . 52 (6): 866–893. дои : 10.1145/1101821.1101823 . S2CID   6238832 . Проверено 5 марта 2010 г.
• Динур, Ирит ; Хот, Субхаш ; Киндлер, Гай; Минцер, Дор; Сафра, Мули (2018). «К доказательству гипотезы игр 2 к 1?». В Диакониколасе, Илиас; Кемпе, Дэвид; Хензингер, Моника (ред.). Материалы 50-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2018, Лос-Анджелес, Калифорния, США, 25-29 июня 2018 г. Ассоциация вычислительной техники. стр. 376–389. дои : 10.1145/3188745.3188804 . ЕССС   ТР16-198 .
• Динур, Ирит ; Сафра, Самуэль (2005). «О сложности аппроксимации минимального вершинного покрытия». Анналы математики . 162 (1): 439–485. CiteSeerX   10.1.1.125.334 . дои : 10.4007/анналы.2005.162.439 .
• Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности . Спрингер. дои : 10.1007/3-540-29953-X . ISBN  978-3-540-29952-3 . Проверено 5 марта 2010 г.
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1977). «Задача о прямолинейном дереве Штейнера NP-полна». SIAM Journal по прикладной математике . 32 (4): 826–834. дои : 10.1137/0132071 .
• Гэри, Майкл Р .; Джонсон, Дэвид С. (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . У. Х. Фриман. ISBN  0-7167-1045-5 . A1.1: GT1, стр. 190.
• Гэри, Майкл Р .; Джонсон, Дэвид С .; Стокмейер, Ларри (1974). «Некоторые упрощенные NP-полные задачи» . Материалы шестого ежегодного симпозиума ACM по теории вычислений . стр. 47–63. дои : 10.1145/800119.803884 .
• Галлай, Тибор (1959). «О множествах крайних точек и ребер». Энн. Университет наук. Будапешт, квартал Этвёш. Математика . 2 : 133-138.
• Каракостас, Джордж (ноябрь 2009 г.). «Лучший коэффициент аппроксимации для задачи вершинного покрытия» (PDF) . Транзакции ACM на алгоритмах . 5 (4): 41:1–41:8. CiteSeerX   10.1.1.649.7407 . дои : 10.1145/1597036.1597045 . S2CID   2525818 . ЕССС   ТР04-084 .
• Карпински, Марек; Зеликовский, Александр (1998). «Аппроксимация плотных случаев покрытия задач» . Материалы семинара DIMACS по проектированию сетей: возможности подключения и расположение объектов . Серия DIMACS по дискретной математике и теоретической информатике. Том. 40. Американское математическое общество. стр. 169–178.
• Хот, Субхаш ; Минцер, Дор; Сафра, Мули (2017). «О независимых множествах, играх 2 к 2 и графах Грассмана». В Хатами Хамед; Маккензи, Пьер; Кинг, Валери (ред.). Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений, STOC 2017, Монреаль, Квебек, Канада, 19–23 июня 2017 г. Ассоциация вычислительной техники. стр. 576–589. дои : 10.1145/3055399.3055432 . ЕССС   ТР16-124 .
• Хот, Субхаш ; Минцер, Дор; Сафра, Мули (2018). «Псевдослучайные множества в графе Грассмана имеют почти идеальное расширение» . 59-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2018 г. стр. 592–601. дои : 10.1109/FOCS.2018.00062 . ISBN  978-1-5386-4230-6 . S2CID   3688775 .
• Хот, Субхаш ; Регев, Одед (2008). «Покрытие вершин может быть трудно аппроксимировать с точностью до 2−ε» . Журнал компьютерных и системных наук . 74 (3): 335–349. дои : 10.1016/j.jcss.2007.06.019 .
• Пападимитриу, Христос Х .; Стейглиц, Кеннет (1998). Комбинаторная оптимизация: алгоритмы и сложность . Дувр.
• Vazirani, Vijay V. (2003). Approximation Algorithms . Springer-Verlag. ISBN  978-3-662-04565-7 .

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

• Вайсштейн, Эрик В. «Вертексная крышка» . Математический мир .
• Вайсштейн, Эрик В. «Минимальное покрытие вершин» . Математический мир .
• Вайсштейн, Эрик В. «Номер покрытия вершины» . Математический мир .
• Переправы через реки (и числа Алкуина) – Numberphile