Offene Probleme im Zusammenhang mit der Graphisomorphie

18

Gegenwärtig mache ich eine Literaturübersicht über das Problem des Graphisomorphismus (GI).

Ich würde gerne einige offene Fragen zu folgenden Themen haben

  1. Was sind die Graphparameter, für die die Traktierbarkeit fester Parameter von GI ein offenes Problem ist?

  2. Was sind die Graph-Parameter, durch deren Festlegung die polynomielle Zeitlösbarkeit von GI nicht bekannt ist.

  3. Die Komplexität von GI bei Beschränkung auf viele Grafikklassen entspricht der allgemeinen GI (GI-Vollständigkeit). Für welche Grafikklassen ist die GI-Vollständigkeit nicht bekannt.

Vielen Dank.

graph-isomorphism fixed-parameter-tractable Kumar
quelle
3
Mir sind keine endgültigen Antworten auf Ihre Fragen bekannt. Wenn Sie Teilantworten finden (für die möglicherweise ein Blick auf Dutzende von veröffentlichten Forschungsarbeiten erforderlich ist), ist es hilfreich, wenn Sie auf die von Ihnen erstellte Zusammenfassung verweisen oder deren Höhepunkte als Antwort angeben.
András Salamon
Zu 3, Frage. Ist die Frage "Sind nicht- Diagramme GI vollständig?" für die vielen Diagrammklassen vollständig? öffnen? Macht das irgendeinen Sinn? Verwandte cs.se FrageXXX
vzn

Antworten:

13

Zur ersten Frage: Der Graphisomorphismus wurde für mindestens die folgenden Parameter berücksichtigt, für die die Traktierbarkeit mit festen Parametern noch offen ist.

  • pathwidth / Baumweite (siehe [2], wurde gefragt , hier ), vielleicht gelöst: http://arxiv.org/abs/1404.0818
  • Schnittbreite / Bandbreite [1]
  • Größe der Scheitelpunkt-Löschmenge (Rückkopplungsscheitelpunkt-Satznummer in [7])
  • Baum- / Wegdistanzbreite (siehe [1]), zusammenhängende Baumdistanzbreite (siehe [3]), jedoch kann man der letzten sehr nahe kommen, siehe Abschnitt 6.4 meiner Diplomarbeit ) : gelöst von Y. Otachi und P Schweitzer: http://arxiv.org/abs/1403.7238
  • Clique-Breite / Strauch-Tiefe (oder SC-Tiefe) (siehe [ 4 ])
  • Maximaler Grad [5]
  • Gattung [6] / Kreuzungsnummer [8]

Beachten Sie, dass für einige von ihnen derzeit aktive Forschungsarbeiten durchgeführt werden.

[1]: K. Yamazaki, HL Bodlaender, B. de Fluiter und DM Thilikos. Isomorphismus für Graphen mit begrenzter Abstandsbreite. Algorithmica 24.2 (1999)

[2]: HL Bodlaender. Polynomalgorithmen für den Isomorphismus und den chromatischen Index von Partialk-Bäumen. Journal of Algorithms 11.4 (1990)

[3]: Y. Otachi. Isomorphismus für Graphen mit begrenzter Verbunden-Pfad-Distanz-Breite. Algorithmen und Berechnung. Springer, 2012

[ 4 ]: http://www.fi.muni.cz/~hlineny/res-en.html#recent

[5]: L. Babai und EM Luks. Kanonische Kennzeichnung von Grafiken. STOC '83.

[6]: IS Filotti und JN Mayer. Ein Polynom-Zeit-Algorithmus zur Bestimmung des Isomorphismus von Graphen fester Gattungen. STOC '80 / G. Miller. Isomorphismustest für Diagramme der begrenzten Klasse. STOC '80

[7]: S. Kratsch und P. Schweitzer. Isomorphismus für Graphen mit der eingestellten Zahl des begrenzten Feedback-Scheitelpunkts. SWAT 2010

[8]: http://math.mit.edu/news/summer/SPURprojects/2012Velednitsky.pdf

frafl
quelle
1
In Bezug auf aktive relevante Forschung in diesem Bereich gibt es einige zusätzliche Referenzen, die ich vorschlagen würde. [A] Dieses Papier hier von IPEC 2012 zeigt Graphisomorphie wird fest Parameter tractable in der Baum- Tiefe eines Graphen, der ein Parameter zum Baumbreite bezogen ist. [B] Das Papier hier zeigt , dass Graphisomorphie für Akkord-Diagramme FPT in der Größe der größten simplizialer Komponente ist.
Adam Bouland
3
Eine weitere Referenz ist dieses Papier aus STOC '08, das sehr nahe daran liegt, zu zeigen, dass der Graphisomorphismus eine FPT in der Gattung eines Graphen ist. Insbesondere zeigen sie, dass der Graphisomorphismus in linearer Zeit vorliegt, wenn er auf die Klasse von Graphen beschränkt ist, die eine polyedrische Einbettung in eine feste Oberfläche der Gattung zulassen . gSg
Adam Bouland
@Adam Bouland Gibt es FPT- oder Polynomial-Zeitalgorithmen für den Graph-Isomorphismus für die begrenzte Bandbreite?
Kumar
1
@Kumar Es ist mehrfach lösbar, aber nicht als FPT bekannt. Siehe Yamazaki et al. [1] in der antwort von frafl.
Yota Otachi
5

Zur dritten Frage: Die Übersichtsarbeit von Brandstadt, Le, und Spinrad, Graph Classes: A Survey, SIAM, 1999, enthält mehrere Graphklassen, für die die GI-Vollständigkeit nicht bekannt ist. Eine solche Klasse sind Trapezgraphen . Eine weitere Klasse sind Kreisbogengraphen, die in der Einführung der Arbeit Tractabilities and Intractabilities on Geometric Intersection Graphs von Uehara als offenes Problem erwähnt werden .

BEARBEITEN : Es ist nicht bekannt, dass das Graph Isomorphism-Problem für Turniere vollständig ist.

Mohammad Al-Turkistany
quelle
4

Für die dritte Frage können Sie auch einen Blick auf www.graphclasses.org werfen : Starten Sie das Java-Applet und wählen Sie Probleme -> Grenze / Offene Probleme -> Graphisomorphie.

Sie erhalten eine große Liste von Diagrammklassen, deren GI-Problemstatus ISGCI nicht bekannt ist (möglicherweise in P oder GI-complete). wahrscheinlich ist für einige von ihnen die GI-Vollständigkeit bereits festgelegt oder sie sind einfach noch nicht untersucht worden; Aber es ist ein guter Ausgangspunkt, um nach Artikeln über sie zu suchen.

Marzio De Biasi
quelle