Isomorphism and Similarity of Graphs

• Applicant: Professor Dr. Johannes Köbler
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 188403235

• Final Report Year: 2018

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
  
• “Approximate Graph Isomorphism”. In: Proc. 37th MFCS. 2012, pp. 100–111
  V. Arvind, J. Köbler, S. Kuhnert, and Y. Vasudev
  
• “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
  
• “The parallel complexity of Graph Canonization under Abelian group action”. In: Algorithmica 67.2 (2013), pp. 247–276
  V. Arvind and J. Köbler
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “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
  
• “Graph isomorphism, color refinement, and compactness”. In: Comput. Complexity 26.3 (2017)
  V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky