Линейный граф гиперграфа - это (простой) граф G, имеющий ребра H, поскольку вершины с двумя ребрами H смежны в G, если они имеют непустое пересечение. Гиперграф является r- гиперграфом, если каждое из его ребер имеет не более r вершин.
Какова сложность следующей задачи: существует ли граф , для которого существует 3 -гиперграф H такой, что G является линейным графом H ?
Хорошо известно, что распознавание линейных графиков гиперграфа является полиномиальным, и известно (Poljak et al., Discrete Appl. Math. 3 (1981) 301-312), что распознавание линейных графиков r- гиперграфов является NP. -полный для любого фиксированного r ≥ 4 .
Примечание. В случае простых гиперграфов, т. Е. Все гипергибы различны, задача является NP-полной, что доказано в работе Poljak et al.
Ответы:
Я нашел журнальную версию препринта Skums et al. указал @mhum; это здесь: Дискретная математика 309 (2009) 3500–3517 . Там авторы исправили свою цитату следующим образом:
Ссылкой 15 является вышеупомянутый Poljak et al. (1981).
источник
источник