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

Набор узлов гиперграфа, с которыми соединено каждое гиперребро

В теории графов вершинное покрытие в гиперграфе — это набор вершин , такой, что каждое гиперребро гиперграфа содержит по крайней мере одну вершину этого набора. Это расширение понятия вершинного покрытия в графе. ^{[1] : 466–470  [2]}

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

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

Определение

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

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

Число вершинного покрытия (также известное как трансверсальное число ) гиперграфа H — это наименьший размер вершинного покрытия в H. Его часто обозначают как τ ( H ) . ^{[1] : 466}

Например, если 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 . ^[3]

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

Удар по сету и сет-кавер

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

Приложения

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

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

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

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

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

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

В символах:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549
2. Берге, Клод (1973). Графы и гиперграфы . Амстердам: Северная Голландия.
3. Хот, Субхаш ; Регев, Одед (2008). «Покрытие вершин может быть трудно аппроксимировать с точностью до 2−ε». Журнал компьютерных и системных наук . 74 (3): 335–349. doi : 10.1016/j.jcss.2007.06.019 .
4. Флум, Йорг; Гроэ, Мартин (2006). Параметризованная теория сложности. Спрингер. ISBN 978-3-540-29952-3. Получено 2010-03-05 .
5. О'Каллахан, Роберт; Чой, Чон-Док (2003). «Гибридное динамическое обнаружение гонки данных». ACM SIGPLAN Notices . 38 (10): 167–178. doi :10.1145/966049.781528.
6. O'Callahan, Robert; Choi, Jong-Deok (2003). "Hybrid dynamic data race Detection". Труды девятого симпозиума ACM SIGPLAN по принципам и практике параллельного программирования . стр. 167–178. doi :10.1145/781498.781528. ISBN 1-58113-588-2.
7. Л. Ловас (1975). «О соотношении оптимальных интегральных и дробных покрытий». Дискретная математика . 13 (4): 383–390. doi :10.1016/0012-365X(75)90058-8. ISSN  0012-365X. Zbl  0323.05127. Wikidata  Q56391140.
8. Фюреди, Золтан (1981-06-01). «Максимальная степень и дробные паросочетания в однородных гиперграфах». Combinatorica . 1 (2): 155–162. doi :10.1007/BF02579271. ISSN  1439-6912. S2CID  10530732.