Вершинное покрытие в гиперграфах - Vertex cover in hypergraphs

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

Эквивалентный термин - это набор совпадений : для данного набора наборов набор, который пересекает все наборы в коллекции по крайней мере в одном элементе, называется набором совпадений. Эквивалентность можно увидеть, сопоставив множества в коллекции с гиперребрами.

Другой эквивалентный термин, более используемый в комбинаторном контексте, - трансверсальный .

Понятия ударов сета и сета укрытия тоже эквивалентны.

Определение

Напомним, что гиперграф H - это пара ( V , E ), где V - множество вершин, а E - множество подмножеств V, называемых гиперребрами . Каждое гиперребро может содержать одну или несколько вершин.

Вершина-крышка (он же удар множество или трансверсально ) в H устанавливается T  ⊆  V такой , что для всех гиперребры х  ∈  Е , то справедливо , что T  ∩  е  ≠ ∅.

Число вершин-крышка ( так называемый трансверсально номер ) гиперграфа H является наименьшим размером с вершиной в крышке H . Часто обозначается как .

Например, если H - это 3-равномерный гиперграф:

{{1,2,3}, {1,4,5}, {4,5,6}, {2,3,6}}

то H допускает несколько вершинных покрытий размера 2, например:

{1, 6}

Однако ни подмножество размера 1 не попадает все гиперребра из H . Следовательно, число вершинных покрытий H равно 2.

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

Алгоритмы

Вычислительные проблемы минимального набора удара и удар набора определяются как в случае графиков.

Если размер максимума гиперребро ограничивается д , то проблема поиска минимального д -hitting набор позволяет д -аппроксимация алгоритм. Предполагая гипотезу уникальных игр , это лучший алгоритм с постоянным множителем, который возможен, в противном случае есть возможность улучшить приближение к d  - 1.

Для задачи о множестве попаданий имеют смысл различные параметризации . Проблема набора совпадений является W [2] -полной для параметра OPT, то есть маловероятно, что существует алгоритм, работающий за время f (OPT) n O (1), где OPT - мощность наименьшего набора совпадений. . Проблема набора совпадений решается с фиксированным параметром для параметра OPT +  d , где d - размер наибольшего края гиперграфа. В частности, существует алгоритм попадания в множество, который выполняется за время d OPT n O (1) .

Комплект для ударов и комплект крышки

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

Приложения

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

Дробное покрытие вершины

Дробно-вершина крышка является функцией присвоения веса в каждую вершину в V , такой , что для каждых гиперребро е в Е , сумма фракций вершин е , по крайней мере 1. Вершина крышка представляет собой частный случай дробного вершинное покрытие, в котором все веса равны 0 или 1. Размер дробного вершинного покрытия - это сумма долей всех вершин.

Дробно-вершина крышки число гиперграфа H является наименьшим размером с дробной вершины покрова в H . Часто обозначается как .

Поскольку вершинное покрытие является частным случаем дробного вершинного покрытия, для каждого гиперграфа H :

дробное число покрытий вершин ( H ) ≤ число покрытий вершин ( H );

В символах:

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

  • Если каждая вершина содержится не более чем в d гиперребрах (т. Е. Степень гиперграфа не превышает d ), то .

Трансверсали в конечных проективных плоскостях

Конечная проективная плоскость гиперграф , в котором каждые два гиперребра пересекаются. Каждая конечная проективная плоскость r- однородна для некоторого целого r . Обозначим через Н г в R проективную плоскость -равномерная. Известны следующие проективные плоскости:

  • H 2 : это просто треугольный график.
  • H 3 : это самолет Фано .
  • H p + 1 существует всякий раз, когда p степень простого числа.

Когда H r существует, он обладает следующими свойствами:

  • Он имеет r 2 - r +1 вершин и r 2 - r +1 гиперребер.
  • Оно r -равномерно - каждое гиперребро содержит ровно r вершин.
  • Он r -регулярен - каждая вершина содержится ровно в r гиперребрах.
  • : r вершин в каждом гиперребре e является вершинным покрытием H r (так как каждое другое гиперребро пересекает e ).
  • Единственные трансверсали размера r - гиперребра; все остальные трансверсали имеют размер не менее r +2.
  • .
  • : каждое паросочетание в H r содержит не более одного гиперребра.

Минимальные трансверсали

Вершинное покрытие (трансверсаль) T называется минимальным, если никакое собственное подмножество T не является трансверсалью.

Трансверсально Гиперграф из Н является Гиперграфом ( Х , Р ), множество гиперребро Р состоит из всех минимальных-трансверсалей H .

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

Смотрите также

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

  1. ^ a b Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, 29 , Северная Голландия, ISBN 0-444-87916-1, Руководство по ремонту  0859549
  2. Перейти ↑ Berge, Claude (1973). Графы и гиперграфы . Амстердам: Северная Голландия.
  3. ^ Хот, Субхаш ; Регев, Одед (2008). «Покрытие вершины может быть трудно аппроксимировать с точностью до 2-ε» . Журнал компьютерных и системных наук . 74 (3): 335–349. DOI : 10.1016 / j.jcss.2007.06.019 .
  4. ^ Флум, Йорг; Grohe, Мартин (2006). Параметризованная теория сложности . Springer. ISBN 978-3-540-29952-3. Проверено 5 марта 2010 .
  5. ^ О'Каллахан, Роберт; Чой, Чон-Док (2003). «Обнаружение гибридной динамической гонки данных» . Материалы симпозиума ACM SIGPLAN по принципам и практике параллельного программирования (PPoPP 2003) и семинара по частичному вычислению и управлению программами на основе семантики (PEPM 2003) . Уведомления ACM SIGPLAN . 38 (10). С. 167–178. DOI : 10.1145 / 966049.781528 .
  6. ^ Ловаса, Л. (1975-01-01). «О соотношении оптимальных целых и дробных покрытий» . Дискретная математика . 13 (4): 383–390. DOI : 10.1016 / 0012-365X (75) 90058-8 . ISSN  0012-365X .
  7. ^ Furedi, Золтан (1981-06-01). «Максимальные степени и дробные сопоставления в однородных гиперграфах» . Combinatorica . 1 (2): 155–162. DOI : 10.1007 / BF02579271 . ISSN  1439-6912 . S2CID  10530732 .