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

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

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

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

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

Определение

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

А вершина-крышка (он же ударная установка или же поперечный) в ЧАС установлен Т ⊆ V так что для всех гиперребер е ∈ E, считается, что Т ∩ е ≠ ∅.

В номер вершинного покрытия (он же поперечное число) гиперграфа ЧАС наименьший размер вершинного покрытия в ЧАС. Часто обозначается как ${\displaystyle \tau (H)}$.^[1]:466

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

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

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

{1, 6}

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

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

Алгоритмы

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

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

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

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

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

Приложения

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

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

А дробное покрытие вершины функция, назначающая вес в ${\displaystyle [0,1]}$ в каждую вершину в V, что для каждого гиперребра е в E, сумма долей вершин в е не меньше 1. Вершинное покрытие - это частный случай дробного вершинного покрытия, в котором все веса равны 0 или 1. размер дробного вершинного покрытия - это сумма долей всех вершин.

В дробное число вершинного покрытия гиперграфа ЧАС - наименьший размер дробного вершинного покрытия в ЧАС. Часто обозначается как ${\displaystyle \tau ^{*}(H)}$.

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

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

В символах:

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

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

• Если каждая вершина содержится не более чем в d гиперребра (т. е. степень гиперграфа не более d), тогда ${\displaystyle \tau (H)/\tau ^{*}(H)\leq 1+\ln(d)}$.

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

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

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

Когда ЧАС_р существует, он имеет следующие свойства:^[7]

• Она имеет р²-р+1 вершины и р²-р+1 гиперребра.
• это р-униформа - каждое гиперребро содержит ровно р вершины.
• это р-регулярно - каждая вершина содержится ровно в р гиперребра.
• ${\displaystyle \tau (H_{r})=r}$: the р вершины каждого гиперребра е являются вершинным покрытием ЧАС_р (так как любое другое гиперребро пересекает е).
• Единственные трансверсали размера р гиперребры; все остальные трансверсали имеют размер не менее р+2.
• ${\displaystyle \tau ^{*}(H_{r})=\nu ^{*}(H)=r-1+1/r}$.
• ${\displaystyle \nu (H_{r})=1}$: каждое совпадение в ЧАС_р содержит не более одного гиперребра.

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

Вершина-крышка (трансверсальная) Т называется минимальный если нет подходящего подмножества Т является трансверсальной.

В трансверсальный гиперграф из ЧАС гиперграф (Икс, F), у которого множество гипребер F состоит из всех минимальных трансверсалей ЧАС.

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

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

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

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

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