Neue algorithmische Schranken für Isomorphieprobleme über Graphen und andere algebraische Strukturen

• Antragsteller: Professor Dr. Jacobo Torán
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2013 bis 2018
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 225911997

• Erstellungsjahr: 2018

Zusammenfassung der Projektergebnisse

The complexity of the graph isomorphism problem has been studied for a long time. This problem is very special since it is one of the few problems in NP that is not known to be NP-hard nor solvable in polynomial time. Recently several important results, most remarkably a quasi-polynomial time algorithm for the problem from Babai, have renewed the attention towards this problem and motivated new research. In this project we have approached the graph isomorphism problem from different perspectives, improving several aspects connected with its complexity. The most important results achieved are: Connections between the graph isomorphism problem and the area of proof complexity, proving exponential lower bounds for the problem in resolution, which give a theoretical explanation on why the the use of modern SAT-solvers do not help in dealing with the isomorphism problem. Fixed parameterized algorithms for several problems related to the isomorphism of hyper-graphs, exploring the tight border in which these problems become hard. A classification of the complexity of the graph isomorphism problem on several models of succinct input graphs. A first approach to the classification of isomorphism problems on solution graphs of Boolean formulas, where we show that the complexity of the problem is related to the formula structure. These results show once more the richness of the graph isomorphism problem and its connections to many areas of complexity.

Projektbezogene Publikationen (Auswahl)

• On the Resolution Complexity of Graph Non-isomorphism. In: Theory and Applications of Satisfiability Testing - SAT 2013 - 16th International Conference, Helsinki, Finland, July 8-12, 2013. Proceedings. 2013, pp. 52–66
  Jacobo Torán
  
• On the Structure of Solution-Graphs for Boolean Formulas. In: Fundamentals of Computation Theory - 20th International Symposium, FCT 2015, Gdansk, Poland, August 17-19, 2015, Proceedings. 2015, pp. 118–130
  Patrick Scharpfenecker
  
• The Graph Isomorphism Problem (Dagstuhl Seminar 15511), Dagstuhl Reports, volume 5, number 12, pages 1–17, 2015
  László Babai, Anuj Dawar, Pascal Schweitzer, and Jacobo Torán
  
• CNF and DNF succinct graph encodings. In: Information and Computation (2016). issn: 0890-5401
  Bireswar Das, Patrick Scharpfenecker, and Jacobo Torán
  
• Solution-Graphs of Boolean Formulas and Isomorphism. In: Theory and Applications of Satisfiability Testing - SAT 2016 - 19th International Conference, Bordeaux, France, July 5-8, 2016, Proceedings. 2016, pp. 29–44
  Patrick Scharpfenecker and Jacobo Torán
  
• Bounded-Depth Succinct Encodings and the Structure they Imply on Graphs.“ In: Theory of Computing Systems (2017), pp. 1–19. issn: 1433-0490
  Patrick Scharpfenecker
  
• Parameterized Complexity of Small Weight Automorphisms, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, pages 7:1–7:13, March 8-11, 2017, Hannover, Germany
  Vikraman Arvind, Johannes Köbler, Sebastian Kuhnert, and Jacobo Torán
  
• Problems on succinctly encoded graphs, Dissertation, Ulm University, 2017
  Patrick Scharpfenecker