Крышка Vertex - Vertex cover

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

в математический дисциплина теория графов, а крышка вершины (иногда крышка узла) из график - это набор вершин, включающий хотя бы одну конечную точку каждого ребра график.Проблема поиска минимальное покрытие вершины это классический проблема оптимизации в Информатика и является типичным примером NP-жесткий проблема оптимизации, имеющая алгоритм аппроксимации. Его версия решения, то проблема покрытия вершины, был одним из 21 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 тау (К_ {м, п}) = мин {, м, п , }}$ .

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

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

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

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

ЭКЗЕМПЛЯР: График

{ displaystyle G}

ВЫХОД: наименьшее число

{ displaystyle k}

такой, что

{ displaystyle G}

имеет вершинное покрытие размера

{ displaystyle k}

.

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

ЭКЗЕМПЛЯР: График

{ displaystyle G}

и положительное целое число

{ displaystyle k}

.

ВОПРОС: Есть ли

{ displaystyle G}

иметь вершинное покрытие размером не более

{ displaystyle k}

?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Псевдокод

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

^[14]^[15]

Приложения

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

Примечания

^ Вазирани 2003, стр. 121–122
^ Гэри, Джонсон и Стокмейер, 1974 г.
^ Гэри и Джонсон 1977; Гэри и Джонсон 1979, С. 190 и 195.
^ Чен, Кандж и Ся 2006
^ Demaine et al. 2005 г.
^ Flum & Grohe (2006 г.), п. 437)
^ Пападимитриу и Штайглиц 1998, п. 432 упоминает Гаврила и Яннакакиса. Гэри и Джонсон 1979, п. 134, цитирует Гаврила.
^ Каракостас 2009
^ Карпинский и Зеликовский 1998
^ Динур и Сафра 2005
^ Хот, Минцер и Сафра 2017^{[требуется полная цитата ]}
^ Dinur et al. 2018 г.^{[требуется полная цитата ]}
^ Хот и Регев 2008
^ Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001) [1990]. «Раздел 35.1: Проблема покрытия вершины». Введение в алгоритмы (2-е изд.). MIT Press и McGraw-Hill. С. 1024–1027. ISBN 0-262-03293-7.
^ Чакрабарти, Амит (зима 2005 г.). «Алгоритмы аппроксимации: вершинное покрытие» (PDF). Компьютерные науки 105. Дартмутский колледж. Получено 21 февраля 2005.
^ Хоссейн, Аян; Лопес, Эриберто; Хальпер, Шон М .; Cetnar, Daniel P .; Reis, Александр C .; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13.07.2020). «Автоматизированное проектирование тысяч неповторяющихся деталей для разработки стабильных генетических систем». Природа Биотехнологии. Дои:10.1038 / s41587-020-0584-2. ISSN 1087-0156. PMID 32661437. S2CID 220506228.
^ Reis, Александр C .; Хальпер, Шон М .; Vezeau, Grace E .; Cetnar, Daniel P .; Хоссейн, Аян; Clauer, Phillip R .; Салис, Ховард М. (ноябрь 2019 г.). «Одновременная репрессия нескольких бактериальных генов с использованием неповторяющихся массивов сверхдлинных sgRNA». Природа Биотехнологии. 37 (11): 1294–1301. Дои:10.1038 / s41587-019-0286-9. ISSN 1546-1696. PMID 31591552. S2CID 203852115.

внешняя ссылка

[1] Вазирани 2003, стр. 121–122

[2] Гэри, Джонсон и Стокмейер, 1974 г.

[3] Гэри и Джонсон 1977; Гэри и Джонсон 1979, С. 190 и 195.

[4] Чен, Кандж и Ся 2006

[5] Demaine et al. 2005 г.

[6] Flum & Grohe (2006 г.), п. 437)

[7] Пападимитриу и Штайглиц 1998, п. 432 упоминает Гаврила и Яннакакиса. Гэри и Джонсон 1979, п. 134, цитирует Гаврила.

[8] Каракостас 2009

[9] Карпинский и Зеликовский 1998

[10] Динур и Сафра 2005

[11] Хот, Минцер и Сафра 2017^{[требуется полная цитата ]}

[12] Dinur et al. 2018 г.^{[требуется полная цитата ]}

[kr08-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] Хоссейн, Аян; Лопес, Эриберто; Хальпер, Шон М .; Cetnar, Daniel P .; Reis, Александр C .; Стрикленд, Девин; Клавинс, Эрик; Салис, Ховард М. (13.07.2020). «Автоматизированное проектирование тысяч неповторяющихся деталей для разработки стабильных генетических систем». Природа Биотехнологии. Дои:10.1038 / s41587-020-0584-2. ISSN 1087-0156. PMID 32661437. S2CID 220506228.

[17] Reis, Александр C .; Хальпер, Шон М .; Vezeau, Grace E .; Cetnar, Daniel P .; Хоссейн, Аян; Clauer, Phillip R .; Салис, Ховард М. (ноябрь 2019 г.). «Одновременная репрессия нескольких бактериальных генов с использованием неповторяющихся массивов сверхдлинных sgRNA». Природа Биотехнологии. 37 (11): 1294–1301. Дои:10.1038 / s41587-019-0286-9. ISSN 1546-1696. PMID 31591552. S2CID 203852115.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]