Распознавание линейных графиков гиперграфов

20

Линейный граф гиперграфа - это (простой) граф G, имеющий ребра H, поскольку вершины с двумя ребрами H смежны в G, если они имеют непустое пересечение. Гиперграф является r- гиперграфом, если каждое из его ребер имеет не более r вершин.HGHHGrr

Какова сложность следующей задачи: существует ли граф , для которого существует 3 -гиперграф H такой, что G является линейным графом H ?G3HGH

Хорошо известно, что распознавание линейных графиков гиперграфа является полиномиальным, и известно (Poljak et al., Discrete Appl. Math. 3 (1981) 301-312), что распознавание линейных графиков r- гиперграфов является NP. -полный для любого фиксированного r 4 . 2rr4

Примечание. В случае простых гиперграфов, т. Е. Все гипергибы различны, задача является NP-полной, что доказано в работе Poljak et al.

user13136
источник
Возможно, стоит уточнить, что вы разрешаете повторение ребер в гиперграфе.
Андрас Саламон
@Salamon: Спасибо за предложение, я отредактировал соответственно. Извините, но я узнал, что по определению гиперграфы могут иметь несколько ребер!
user13136

Ответы:

8

Я нашел журнальную версию препринта Skums et al. указал @mhum; это здесь: Дискретная математика 309 (2009) 3500–3517 . Там авторы исправили свою цитату следующим образом:

k3k=2L3GLkk4GL3lk33однородные гиперграфы без кратных ребер [15] являются NP-полными.

Ссылкой 15 является вышеупомянутый Poljak et al. (1981).

3

VB Le
источник
Это хорошо знать! Спасибо за уделенное время.
user13136
8

rr34

k=3k=2L3GL3GLklk3

L3L3l

mhum
источник
5
3
Ах. Понимаю. Мне не всегда понятно, включает ли термин «гиперграф» гипермультиграфы (мультигиперграфы?).
mhum
Спасибо за ответ, и извините за мою свободную формулировку.
user13136
@vb le спасибо за ссылку и вклад в мой вопрос!
user13136
5
@ user13136: Добро пожаловать! Это потому, что я знаю людей, включая меня, которые считают, что проблема должна быть NP-полной, но не могут найти ссылку / доказательство.
vb le