Вершинное покрытие в гиперграфах

В теории графов вершинное покрытие гиперграфа , такой, что каждое гиперребро — это набор вершин гиперграфа содержит хотя бы одну вершину этого набора. Это расширение понятия покрытия вершин в графе .

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

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

Определение

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

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

Число вершинного покрытия (также известное как число ) гиперграфа H — это наименьший размер вершинного покрытия в 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.

Алгоритмы

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

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

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

Набор ударов и крышка набора

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

Приложения

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

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

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

Число дробного вершинного покрытия гиперграфа H — это наименьший размер дробного вершинного покрытия в H . Его часто обозначают τ *( H ) .

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

дробное-номер-покрытия-вершины( H ) ≤ номер-покрытия вершины ( H );

В символах:

$\tau ^{*}(H)\leq \tau (H).$

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

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

  ${\frac {\tau (H)}{\tau ^{*}(H)}}\leq 1+\ln(d).$

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

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

• H ₂ : это просто треугольный граф.
• H3 _. это плоскость Фано :
• H _{p +1} существует всякий раз, когда p является степенью простого числа .

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

• Он имеет р ² – r + 1 вершина и r ² – r + 1 гиперребро.
• Оно r -однородно: каждое гиперребро содержит ровно r вершин.
• Он r -регулярен: каждая вершина содержится ровно в r гиперребрах.
• τ ( H _r ) = r : r вершин в каждом гиперребре e являются вершинным покрытием H _r (поскольку каждое другое гиперребро пересекает e ).
• Единственные трансверсали размера r — это гиперребра; все остальные трансверсали имеют размер не менее r + 2 .
• τ *( ЧАС _р ) знак равно ν *( ЧАС ) знак равно р – 1 + ⁠ 1 / r ⁠ .
• ν ( H _r ) = 1 : каждое паросочетание в H _r содержит не более одного гиперребра.

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

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

Трансверсальный гиперграф H множество — это гиперграф ( X , F ), гиперребер F состоит из всех минимальных трансверсалей H. чье

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

См. также

• Сопоставление в гиперграфах - также обсуждается двойственность между покрытием вершин и сопоставлением.