Frontiers of Tractability for Graph Isomorphism and Homomorphism Problems

• Applicant: Dr. Oleg Verbitsky
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 197227691

• Final Report Year: 2016

Final Report Abstract

Die allgemeine Zielvorgabe des Projektes war, die aktuellen Grenzen für die effiziente Lösbarkeit von Isomorphie- und Homomorphie- (d.h. Constraint Satisfaction) Problemen für Graphen zu erweitern. Die beiden Klassen von Problemen können aus einer gemeinsamen Perspektive behandelt werden, wenn man auf die Methoden der Endlichen Modelltheorie setzt, die auf Definierberkeit der Eingabegraphen in geeigneten Fragmenten der Logik der ersten Stufe beruhen. Im Lauf der Arbeit am Projekt stellte sich heraus, dass ähnliche Methoden auch in einem anderen Bereich nützlich sind, nämlich bei der Untersuchung von lokal bijektiven Homomorphismen (oder Überlagungsabbildungen) im Rahmen ihrer Anwendungen auf Verteiltes Rechnen. Diese Ergebnisse gehören zu den wichstigsten Beiträgen des Projektes: In ihrer klassischen Arbeit haben Babai, Erdös, und Selkow gezeigt, dass fast alle Graphen durch das Color-Refinement-Verfahren kanonisierbar sind. Wir geben eine explizite, effizient verifizierbare Beschreibung der Klasse aller Graphen, auf denen Color Refinement gelingt. - In den späten Achtzigern hat Gottfried Tinhofer eine auf linearer Programmierung beruhende Methode für Isomorphie-Testen vorgeschlagen, die auf Integritätseigenschaften des Polytops der fraktionalen Graphenauthomorphismen basiert. Im Zuge unserer Arbeit am Projekt haben wir festgestellt, dass dieser tiefe und geschickte Ansatz nicht so viel Aufmerksamkeit in der Literatur erhalten hat, wie er definitiv verdient, und zu seinem Verständnis beigetragen. Insbesondere haben wir gezeigt, dass die Anwendbarkeitsbereich dieser Methode mindestens so groß ist wie für Color Refinement (und sogar streng größer). - Wir konstruierten Logspace-Isomorphie-Algorithmen für propere und Helly Kreisbogengraphen. Als Nebenprodukt erhielten wir einen Logspace-Algorithmus zum Erkennen, ob eine gegebene Boolesche Matrix die Circular-Ones-Eigenschaft besitzt (dieses Konzept entsteht bei der Analyse zirkularer Genome mit Methoden der Bioinformatik). - Das Arc-Consistency-Checking auf zwei relationalen Strukturen ist eine der beliebtesten Heuristiken für die Constraint-Satifaction-Probleme. Wir bestimmen die optimale Zeitkomplexität für Arc-Consistency-Algorithmen, die auf Constraint-Propagation basieren (alle aktuellen Algorithmen in diesem Bereich sind von dieser Art). - Wir beantworten auf eine von Nancy Norris (1995) gestellte offene Frage im Bereich des Verteilten Rechnens. Unsere Lösung impliziert, dass viele verteilte Algorithmen, die den Isomorphietyp der universellen Überlagung des Netzwerkgraphen berechnen, die optimale Kommunikationsrundenkomplexität haben. Dies offenbart eine überraschende Anwendung der algorithmischen Modelltheorie auf das Verteilte Rechnen.

Publications

• On the speed of constraint propagation and the time complexity of arc consistency testing. In: Proc. of the 38th Int. Symp. on Mathematical Foundations of Computer Science (MFCS’13), Lecture Notes in Computer Science, vol. 8087, pp. 159–170, 2013
  C. Berkholz and O. Verbitsky
  
• Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. ACM Transactions on Computational Logic 16(3):21.1–21.26, 2015
  C. Berkholz, A. Krebs, and O. Verbitsky
  
• On the power of color refinement. Proc. of the 20th Int. Symp. on Fundamentals of Computation Theory (FCT’15), Lecture Notes in Computer Science, vol. 9210, pp. 339–350, 2015
  V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky
  
• On Tinhofer’s linear programming approach to isomorphism testing. Proc. of the 40th Int. Symp. on Mathematical Foundations of Computer Science (MFCS’15), Lecture Notes in Computer Science, vol. 9235, pp. 26–37, 2015
  V. Arvind, J. Köbler, G. Rattan, and O. Verbitsky
  
• Universal covers, color refinement, and two-variable logic with counting quantifiers: Lower bounds for the depth. Proc. of the 30-th ACM/IEEE Symp. on Logic in Computer Science (LICS’15), pp. 689–700, 2015
  A. Krebs and O. Verbitsky
  
• Circular-arc hypergraphs: Rigidity via connectedness. Discrete Applied Mathematics, 2016
  J. K¨bler, S. Kuhnert, and O. Verbitsky
  
• On the isomorphism problem for Helly circular-arc graphs. Information and Computation 247:266—277, 2016
  J. Köbler, S. Kuhnert, and O. Verbitsky
  
• Solving the canonical representation and Star System problems for proper circular-arc graphs in Logspace. Journal of Discrete Algorithms, 2016
  J. Köbler, S. Kuhnert, and O. Verbitsky