Erkennen von Liniendiagrammen von Hypergraphen

Das Liniendiagramm eines Hypergraphen ist das (einfache) Diagramm G mit Kanten von H als Eckpunkten, wobei zwei Kanten von H in G benachbart sind, wenn sie einen nicht leeren Schnittpunkt haben. Ein Hypergraph ist ein r- Hypergraph, wenn jede seiner Kanten höchstens r Eckpunkte hat.$H$$G$$H$$H$$G$$r$$r$

Was ist die Komplexität des folgenden Problems: Gibt es in einem Graphen einen 3- Hypergraphen H, so dass G der Liniendiagramm von H ist ?$G$$3$$H$$G$$H$

Es ist bekannt, dass das Erkennen von Liniendiagrammen von Hypergraphen polynomisch ist, und es ist bekannt (von Poljak et al., Discrete Appl. Math. 3 (1981) 301-312), dass das Erkennen von Liniendiagrammen von r- Hypergraphen NP ist -komplett für jedes feste r ≥ 4 . $2$$r$$r \ge 4$

Anmerkung: Bei einfachen Hypergraphen, dh alle Hyperecken sind unterschiedlich, ist das Problem NP-vollständig, wie in der Arbeit von Poljak et al.

Ich fand die Journalversion des Preprint von Skums et al. wies von @mhum; es ist hier: Discrete Mathematics 309 (2009) 3500–3517 . Dort korrigierten die Autoren ihr Zitat wie folgt:

Die Situation ändert sich radikal, wenn man anstelle von k = 2 nimmt . Lovasz stellte das Problem der Charakterisierung der Klasse L 3 auf und stellte fest, dass es keine Charakterisierung durch eine endliche Liste verbotener induzierter Teilgraphen gibt ( eine endliche Charakterisierung ) [9]. Es wurde bewiesen , dass das Erkennungs problem " G ∈ L k “ für ‚ k ≥ 4 ‘ [15] ‚ G ∈ L l 3 ‘ für k ≥ 3 und das Problem der Erkennung von Kantenschnitt Graphen von $k \ge 3$$k = 2$$L_3$$G \in L_k$$k \ge 4$$G \in L^l_3$$k \ge 3$$3$-einheitliche Hypergraphen ohne Mehrfachkanten [15] sind NP-vollständig.

Referenz 15 ist das zuvor erwähnte Patent von Poljak et al. (1981).

Ich denke also, dass das Erkennen von Liniendiagrammen von Hypergraphen (mit mehreren zulässigen Kanten) ein OFFENES PROBLEM ist , und die Antwort von @ mhum war in der Tat hilfreich für diesen Befund. Vielen Dank!$3$

Ich habe keinen Zugang zu Poljak et al. Papier, aber die Zusammenfassung hier scheint darauf hinzudeuten, dass das Erkennen von Liniendiagrammen von Hypergraphen für NP-vollständig ist$r$, nicht für 4 . Auch das Zitieren in Kantenschnittgraphen von linearen 3-einheitlichen Hypergraphen , Skums et al. (pdf)scheint darauf hinzuweisen, dass dies der Fall ist:$r \geq 3$$4$

Die Situation ändert sich hauptsächlich, wenn man anstelle von k = 2 nimmt . Lovasz stellte das Problem der Charakterisierung der Klasse L 3 auf und stellte fest, dass es keine Charakterisierung durch eine endliche Liste verbotener induzierter Teilgraphen gibt ( eine endliche Charakterisierung ) [10]. Es hat sich gezeigt , dass die Erkennung von Problemen " G ∈ L 3 " [17] und " G ∈ L l k " für k ≥ 3 [5] sind NP-vollständig.$k=3$$k=2$$L_3$$G \in L_3$$G \in L^l_k$$k\geq3$

Referenz 17 in dieser Veröffentlichung ist das zuvor erwähnte Patent von Poljak et al. (1981). ist die Klasse der 3-einheitlichen Hypergraphen und $L_3$ ist die Klasse der linearen 3-uniform Hypergraphen.$L^l_3$