Untersuchung der Komplexität des Graphenisomorphieproblems

• Applicant: Professor Dr. Jacobo Torán
• Subject Area: Theoretical Computer Science
• Term: from 2005 to 2011
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 5436983

• Final Report Year: 2010

Final Report Abstract

Wir sind in der Forschung der Komplexität des Isomorphieproblems für Graphen und andere algebraische Strukturen ein Stück weiter gekommen. Insbesondere für konkrete eingeschränkte Graphklassen wie planare, K3,3 und K5 freie Graphen haben wir wichtige Resultate erzielt die das Klassifikationsproblem endgültig lösen können, indem wir die Vollständigkeit der Probleme für die Klasse L bewiesen haben. Auch für das Isomorphieproblem für Quasigruppen haben wir wichtige Resultate erzielt. Intuitiv schien das Problem einfacher als das Graphenisomorphieproblem zu sein. Wir konnten diese Intuition formalisieren und ohne jegliche unbewiesene Voraussetzungen zeigen, dass das erste Problem auf das zweite AC^0 reduzierbar ist, aber Graphenisomorphie nicht auf Quasigruppenisomorphie reduzierbar ist.

Publications

• Arthur-Merlin Games and the Problem of Isomorphism Testing. Proc. Conference on Computability in Europe, Vol. 1, LNCS 3526, 495-506, 2005
  Jacobo Torán
  
• Isomorphism Testing: Perspective and Open Problems. In: Bulletin of the European Association for Theoretical Computer Science, Vol 86, 2005
  V. Arvind and Jacobo Torán
  
• The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem. Proc. 17th International Symposium on Algorithms and Computation, LNCS 4288, 233-242, 2006
  V. Arvind and Jacobo Toran
  
• Hardness results for tournament isomorphism and automorphism. In: 32nd International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 572-583, 2007
  Fabian Wagner
  
• The Quantum Query Complexity of Algebraic Properties. Proc. 16th International Symposium on Fundamentals of Computation Theory, 2007
  Sebastian Dörn, Thomas Thierauf
  
• Hardness results for isomorphism and automorphism of bounded valence graphs. In: Theory and Practice of Computer Science (SOFSEM), volume 2 - Student Research Forum, pages 131-140, 2008
  Fabian Wagner
  
• Isomorphism and factorization, classical and quantum algorithms. Mathematical Analysis of Evolution, Information, and Complexity, 16:433-454, 2009
  Sebastian Dörn, Daniel Haase, Jacobo Torán, and Fabian Wagner
  
• Isomorphism for K3,3-free and K5-free graphs is in log-space. In: Proceedings of the 29th annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2009
  Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf and Fabian Wagner
  
• Planar graph isomorphism is in log-space. Annual IEEE Conference on Computational Complexity (CCC), pages 203-214, 2009
  Samir Datta, Nutan Limaye, Prajalcta Nimbhorkar, Thomas Thierauf and Fabian Wagner
  
• Reachabihty in K3,3-free graphs and K5-free graphs is in unambiguous log-space. In: 17th International Symposium, Fundamentals of Computation Theory (FCT), LNCS 5699, 2009
  Thomas Thierauf and Fabian Wagner
  
• The complexity of planar graph isomorphism. Bulletin of the European Association for Theoretical Computer Science (EATCS), 97:60-82, 2009
  Jacobo Torán and Fabian Wagner
  
• On the complexity of isomorphism testing for restricted classes of graphs. Dissertation. Technical Report VTS-ID/7264, Institutional Repository of University of Ulm, 2010
  Fabian Wagner
  
• Reductions to Graph Isomorphism. Theory of Computing Systems 47 (1) 288-299 (2010)
  Jacobo Torán
  
• Restricted space algorithms for isomorphism on bounded treewidth graphs. In: 27th International Symposium on Theoretical Aspects of Computer Science (STACS), pages 227-238, 2010
  Bireswar Das, Jacobo Torán, and Fabian Wagner
  
• The isomorphism problem for planar 3-connected graphs is in unambiguous logspace. Theory of Computing Systems (ToC), 47(3):655-673, 2010
  Thomas Thierauf and Fabian Wagner