Erkennen von Liniendiagrammen von Hypergraphen

20

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.HGHHGrr

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 ?G3HGH

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 . 2rr4

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

user13136
quelle
Es ist möglicherweise klärenswert, dass Sie wiederholte Kanten in einem Hypergraphen zulassen.
András Salamon
@Salamon: Danke für den Vorschlag, den ich entsprechend bearbeitet habe. Es tut mir leid, aber ich habe erfahren, dass Hypergraphen per Definition mehrere Kanten haben können!
user13136

Antworten:

8

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 3k3k=2L3GLkk4GL3lk33-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

vb le
quelle
Das ist gut zu wissen! Vielen Dank für Ihre Zeit.
user13136
8

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 istr, 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:r34

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=3k=2L3GL3GLklk3

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 LL3 ist die Klasse der linearen 3-uniform Hypergraphen.L3l

mhum
quelle
5
Das Papier Poljak et al. (1981) erweist sich die folgenden speziellen Fall (Satz 2.2): Erkennen , wenn eine grafische Darstellung der Liniendiagramm eines ist -hypergraph mit allen Hyperkanten sind verschieden ist NP-vollständig. Das Zitat von Skums et al. scheint falsch zu sein. 3
user13136
Ah. Aha. Es ist mir nicht immer klar, ob der Begriff "Hypergraph" Hypermultigraphien (Multihypergraphien?) Umfasst.
mhum
Vielen Dank für Ihre Antwort und entschuldigen Sie meine lose Formulierung.
user13136
@vb le danke für die Verlinkung und Investition in meine Frage!
user13136
5
@ user13136: Gern geschehen! Dies liegt daran, dass ich Leute kenne, einschließlich mir, die glauben, dass das Problem NP-vollständig sein sollte, aber keine Referenz / keinen Beweis finden können.
VB Le