Isomorphism and Similarity of Graphs
Final Report Abstract
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.
Publications
- “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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at 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
(See online at https://doi.org/10.1007/s00037-016-0147-6)
