Isomorphie und Ähnlichkeit von Graphen
Zusammenfassung der Projektergebnisse
Das Graphisomorphieproblem (kurz GI) ist einer der wenigen verbliebenen natürlichen Kandidaten für ein NP-Problem, das weder in P liegt, noch NP-vollständig ist. Im Rahmen dieses Projektes haben wir neue Algorithmen für Einschränkungen von GI auf bestimmte Graphklassen entwickelt. So konnten wir das Isomorphieproblem für k-Bäume, Intervallgraphen und bestimmte Kreisbogengraphen als L-vollständig klassifizieren. Für gefärbte Hypergraphen haben wir einen FPT-Algorithmus entwickelt, wobei die maximale Farbklassengröße als Parameter fungiert. Für den klassischen Farbverfeinerungsalgorithmus (auch als 1-dimensionaler Weisfeiler-Lehman-Algorithmus bekannt), der einen wichtigen Baustein der in der Praxis eingesetzten Isomorphiealgorithmen bildet, haben wir untersucht, für welche Graphen dieser Algorithmus das Isomorphieproblem korrekt entscheidet. Wir konnten zeigen, dass diese Frage in Polynomialzeit entscheidbar ist. Um den Farbverfeinerungsalgorithmus für allgemeinere Graphklassen nutzbar zu machen, wird er häufig in Kombination mit der Individualisierung einzelner Knoten angewandt. Da der Rechenaufwand mit der Anzahl der individualisierten Knoten stark zunimmt, wird eine möglichst kleine Zahl von Individualisierungen angestrebt. Wir konnten zeigen, dass eine Minimierung der Individualisierungen bei Graphen mit Farbklassengröße höchstens 3 effizient möglich ist (sogar in Logspace), ab Farbklassengröße 4 jedoch W[P]-hart wird. Einen weiteren Schwerpunkt unserer Ergebnisse bildet die Ähnlichkeit von Graphen. Für den Fall, dass zwei Hypergraphen isomorph sind und sich nur durch wenige Knotennamen unterscheiden, geben wir einen FPT-Algorithmus an, wobei die Anzahl der umbenannten Knoten sowie wahlweise die Hyperkantengröße oder die maximale Farbklassengröße Parameter sind. Außerdem haben wir den Fall untersucht, dass die Eingabegraphen nicht isomorph sind und ihre Kanten durch eine Knotenpermutation möglichst weitgehend in Übereinstimmung gebracht werden sollen. Wir geben einen Approximationsalgorithmus an, der in Quasipolymonialzeit den optimalen Anteil der Übereinstimmungen bis auf einen beliebig wählbaren konstanten Faktor bestimmt.
Projektbezogene Publikationen (Auswahl)
- “Interval graphs: Canonical representations in logspace”. In: SIAM J. Comput. 40.5 (2011), pp. 1292–1315
J. Köbler, S. Kuhnert, B. Laubner, and O. Verbitsky
(Siehe online unter https://doi.org/10.1137/10080395X) - “Approximate Graph Isomorphism”. In: Proc. 37th MFCS. 2012, pp. 100–111
V. Arvind, J. Köbler, S. Kuhnert, and Y. Vasudev
(Siehe online unter https://doi.org/10.1007/978-3-642-32589-2_12) - “The isomorphism problem for k-trees is complete for logspace”. In: Inf. Comp. 217 (2012), pp. 1–11
V. Arvind, B. Das, J. Köbler, and S. Kuhnert
(Siehe online unter https://doi.org/10.1016/j.ic.2012.04.002) - “The parallel complexity of Graph Canonization under Abelian group action”. In: Algorithmica 67.2 (2013), pp. 247–276
V. Arvind and J. Köbler
(Siehe online unter https://doi.org/10.1007/s00453-013-9805-0) - “Colored Hypergraph Isomorphism is fixed parameter tractable”. In: Algorithmica 71.1 (2015), pp. 120–138
V. Arvind, B. Das, J. Köbler, and S. Toda
(Siehe online unter https://doi.org/10.1007/s00453-013-9787-y) - “Interval graph representation with given interval and intersection lengths”. In: J. Discr. Algor. 34 (2015), pp. 108–117
J. Köbler, S. Kuhnert, and O. Watanabe
(Siehe online unter https://doi.org/10.1016/j.jda.2015.05.011) - “On the isomorphism problem for decision trees and decision lists”. In: Theor. Comput. Sci. 590 (2015), pp. 38–54
V. Arvind, J. Köbler, S. Kuhnert, G. Rattan, and Y. Vasudev
(Siehe online unter https://doi.org/10.1016/j.tcs.2015.01.025) - “On the isomorphism problem for Helly circular-arc graphs”. In: Inf. Comp. 247 (2016), pp. 266–277
J. Köbler, S. Kuhnert, and O. Verbitsky
(Siehe online unter https://doi.org/10.1016/j.ic.2016.01.006) - “Solving the canonical representation and star system problems for proper circular-arc graphs in logspace”. In: J. Discr. Algor. 38-41 (2016), pp. 38–49
J. Köbler, S. Kuhnert, and O. Verbitsky
(Siehe online unter https://doi.org/10.1016/j.jda.2016.03.001) - “The parameterized complexity of fixing number and vertex individualization in graphs”. In: Proc. 41st MFCS. 2016, 13:1–13:14
V. Arvind, F. Fuhlbrück, J. Köbler, S. Kuhnert, and G. Rattan
(Siehe online unter https://doi.org/10.4230/LIPIcs.MFCS.2016.13) - “Finding Small Weight Isomorphisms with Additional Constraints is Fixed-Parameter Tractable”. In: Proc. 12th IPEC. 2017, 2:1–2:12
V. Arvind, J. Köbler, S. Kuhnert, and J. Torán
(Siehe online unter https://doi.org/10.4230/LIPIcs.IPEC.2017.2) - “Graph isomorphism, color refinement, and compactness”. In: Comput. Complexity 26.3 (2017)
V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky
(Siehe online unter https://doi.org/10.1007/s00037-016-0147-6)
