+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Montag, 14. Juni 2021, 16:00 Uhr Ort: Zoom Videokonferenz Link: https://rwth.zoom.us/j/94470149252?pwd=ZnYwVXQrbStveVdDNDk1V1BlN1lJUT09 Meeting-ID: 944 7014 9252 Kenncode: 004247 Referent: Daniel Wiebking, M.Sc. Lehrstuhl Informatik 7 Thema: A Decomposition-Compatible Canonization Framework for the Graph Isomorphism Problem Abstract: The Graph Isomorphism Problem is one of a few famous problems in NP that is neither known to be solvable in polynomial time nor to be NP-complete. The problem asks whether two given input graphs are structurally equivalent, which means that both graphs coincide up to a renaming of the vertices. With Babai's celebrated breakthrough (STOC 2016) it was shown that the problem can be decided in quasipolynomial time. One way of solving the Graph Isomorphism Problem is by applying a canonization approach. Graph canonization is the task of transforming a graph into a canonical form, that is, a graph representation that coincides for structurally equivalent graphs. As far as we know, graph canonization might be harder than the Graph Isomorphism Problem. In particular, there are isomorphism tests for various graph classes and objects for which to date no canonization algorithm with the same asymptotic running time is known. In this thesis, we devise a unified canonization framework for graphs, and beyond that for combinatorial objects in general. We use that framework to design new fastest canonization algorithms with an asymptotic running time matching the best known isomorphism tests. Our framework supports the use of decomposition techniques. By combining our framework with new graph-theoretic decompositions, we not only match but even improve the running time of existing isomorphism tests for graphs of bounded treewidth and graphs excluding fixed minors. Our improved algorithms for restricted graph classes come hand in hand with new insights about the automorphism groups. We prove several restrictions on these groups by analyzing them from a purely mathematical point of view. Beyond that, our decomposition-friendly framework has also applications in computational group theory. In particular, we design a new fastest algorithm computing normalizers of permutation groups. Finally, we investigate the connections between isomorphism testing and canonization from a logical perspective. To this end, we provide a new computation model that supports a construction turning isomorphism tests into canonization algorithms. Es laden ein: die Dozentinnen und Dozenten der Informatik