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

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

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

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

В информатике проблема нахождения минимального вершинного покрытия является классической задачей оптимизации . Это 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 \tau }$ ${\displaystyle \tau =|V'|}$

Примеры

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

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

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

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

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

ПРИМЕР: Граф ${\displaystyle G}$

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

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

ПРИМЕР: график и положительное целое число . ${\displaystyle G}$ ${\displaystyle k}$

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

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

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

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

Эта 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] и даже в планарных графах степени не выше 3. ^[4]

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

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

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

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

Однако для плоских графов и, в более общем смысле, для графов, исключающих некоторый фиксированный граф в качестве минорного, вершинное покрытие размера k может быть найдено за время , т. е. проблема решается субэкспоненциально с фиксированным параметром . ^[6] Этот алгоритм снова является оптимальным в том смысле, что согласно гипотезе экспоненциального времени ни один алгоритм не может решить покрытие вершин на плоских графах за время . ^[7] ${\displaystyle 2^{O({\sqrt {k}})}n^{O(1)}}$ ${\displaystyle 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 раза превышает оптимальное вершинное покрытие.

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

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

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

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

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

Псевдокод

ПРИБЛИЖЕНИЕ - ВЕРШИНА - ПОКРЫТИЕ ( G ) C знак равно ∅ E ' знак равно G . Э   в то время как E ' ≠ ∅ : пусть ( u , v ) будет произвольным ребром E ' C = C ∪ { u , v } удалить из E ' каждое ребро , инцидентное либо u , либо v                             вернуть С 

^{[14] [15]}

Приложения

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

Примечания

1. Галлай 1959.
2. Вазирани 2003, стр. 121–122.
3. Гари, Джонсон и Стокмейер, 1974 г.
4. Гэри и Джонсон 1977; Гари и Джонсон 1979, стр. 190 и 195.
5. Чен, Кандж и Ся, 2006 г.
6. Демейн и др. 2005 г.
7. Флум и Гроэ (2006, стр. 437)
8. Пападимитриу и Стейглиц 1998, стр. 432, упоминает и Гаврила, и Яннакакиса. Гари и Джонсон 1979, с. 134, цитирует Гаврила.
9. Каракостас 2009 г.
10. Карпинский и Зеликовский 1998 г.
11. Динур и Сафра 2005 г.
12. Хот, Минцер и Сафра 2017; Динур и др. 2018 год; Хот, Минцер и Сафра 2018
13. Хот и Регев, 2008 г.
14. Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001) [1990]. «Раздел 35.1: Проблема вершинного покрытия». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. стр. 1024–1027. ISBN 0-262-03293-7.
15. Чакрабарти, Амит (зима 2005 г.). «Алгоритмы аппроксимации: покрытие вершин» (PDF) . Информатика 105 . Дартмутский колледж . Проверено 21 февраля 2005 г.
16. Хоссейн, Аяан; Лопес, Эриберто; Халпер, Шон М.; Цетнар, Дэниел П.; Рейс, Александр К.; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13 июля 2020 г.). «Автоматическое проектирование тысяч неповторяющихся деталей для разработки стабильных генетических систем». Природная биотехнология . 38 (12): 1466–1475. дои : 10.1038/s41587-020-0584-2. ISSN  1087-0156. PMID  32661437. S2CID  220506228.
17. Рейс, Александр С.; Халпер, Шон М.; Везо, Грейс Э.; Цетнар, Дэниел П.; Хоссейн, Аяан; Клауэр, Филипп Р.; Салис, Ховард М. (ноябрь 2019 г.). «Одновременная репрессия нескольких бактериальных генов с использованием неповторяющихся сверхдлинных массивов sgRNA». Природная биотехнология . 37 (11): 1294–1301. дои : 10.1038/s41587-019-0286-9. ISSN  1546-1696. OSTI  1569832. PMID  31591552. S2CID  203852115.

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

• Чен, Цзянер; Кандж, Ияд А.; Ся, Ге (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). «Über Extreme Punkt- und Kantenmengen». Анна. унив. наук. Будапешт, квартал Этвёш. Математика . 2 : 133–138.
• Каракостас, Джордж (ноябрь 2009 г.). «Лучший коэффициент аппроксимации для задачи вершинного покрытия» (PDF) . Транзакции ACM на алгоритмах . 5 (4): 41:1–41:8. CiteSeerX  10.1.1.649.7407 . дои : 10.1145/1597036.1597045. S2CID  2525818. ECCC  TR04-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. doi : 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). Комбинаторная оптимизация: алгоритмы и сложность . Дувр.
• Вазирани, Виджай В. (2003). Алгоритмы аппроксимации . Спрингер-Верлаг. ISBN 978-3-662-04565-7.

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

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