Крышка Vertex

Пример графа, у которого есть вершинное покрытие из 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\,\}}$

Свойства [ править ]

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

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

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

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

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

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

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

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

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

Формулировка ПДОДИ [ править ]

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

свести к минимуму	${\displaystyle \sum _{v\in V}c(v)x_{v}}$			(минимизировать общую стоимость)
при условии	${\displaystyle x_{u}+x_{v}\geq 1}$	для всех ${\displaystyle \{u,v\}\in 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-полным даже в кубических графах ^[2] и даже в плоских графах степени не выше 3. ^[3]

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

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

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

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

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

Приблизительная оценка [ править ]

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

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

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

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

Неприблизимость [ править ]

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

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

Псевдокод [ править ]

Аппроксимация - VERTEX - ПОКРЫТИЕ ( G ) = C  =  ∅ Е ' =  G . Eв то время как  E '  ≠  ∅ :  пусть  ( U ,  V )  будет  произвольное ребро из é ' C = C ∪ { U , V } удалить из Е ' каждого ребра падающего на любом U или V                     вернуть  C

^{[14] [15]}

Приложения [ править ]

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

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

Викискладе есть средства массовой информации, связанные с проблемой покрытия Vertex .

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