Neue algorithmische Schranken für Isomorphieprobleme über Graphen und andere algebraische Strukturen
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
(Siehe online unter https://dx.doi.org/10.1007/978-3-642-39071-5_6) - 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
(Siehe online unter https://dx.doi.org/10.1007/978-3-319-22177-9_10) - 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
(Siehe online unter https://dx.doi.org/10.4230/DagRep.5.12.1) - CNF and DNF succinct graph encodings. In: Information and Computation (2016). issn: 0890-5401
Bireswar Das, Patrick Scharpfenecker, and Jacobo Torán
(Siehe online unter https://doi.org/10.1016/j.ic.2016.06.009) - 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
(Siehe online unter https://doi.org/10.1007/978-3-319-40970-2_3) - 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
(Siehe online unter https://doi.org/10.1007/s00224-017-9787-4) - 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
(Siehe online unter https://dx.doi.org/10.4230/LIPIcs.STACS.2017.7) - Problems on succinctly encoded graphs, Dissertation, Ulm University, 2017
Patrick Scharpfenecker
(Siehe online unter https://dx.doi.org/10.18725/OPARU-4390)
