Informatik, TU Wien

The Graph Isomorphism Problem

Talk by Prof. Martin Grohe, RWTH Aachen University, hosted by the Algorithms and Complexity Group at the Institute for Logic and Computation.

A new million dollar question? One of the most famous problems in theoretical computer science which is practically relevant to combinatorial search and optimization problems remains wide open. The Algorithms and Complexity Group at the Institute for Logic and Computation is proud to host Martin Grohe´s talk on The Graph Isomorphism Problem.

The question of whether there is a polynomial time algorithm deciding if two graphs are isomorphic has been a one of the best known open problems in theoretical computer science for more than forty years. Indeed, the graph isomorphism problem is one of the very few natural problems in NP that is neither known to be in P nor known to be NP-complete. Three years ago, Babai (STOC 2016) gave a quasipolynomial time isomorphism algorithm. Despite of this breakthrough result, the question for a polynomial algorithm remains wide open. The first part of Martin Grohe´s talk will be a survey on the isomorphism problem. In the second part of the talk, he will speak about recent progress, starting from Babai's result and moving on to a new improvement for graphs of small maximum degree (G., Neuen, Schweitzer, FOCS 2018).

Martin Grohe

Martin Grohe studied mathematics in Freiburg, received his doctorate there in 1994 and returned to Freiburg after research stays at the University of California at Santa Cruz and at Stanford University. Martin Grohe has already shaped his field of research, finite model theory. Thus, in his dissertation he completely solved the so-called hierarchy problem for fixed-point logics, in which over a decade only fragmentary insights had been achieved. (Source German Research Foundation (DFG))

Since the early 1980s, theoretic investigation of the problem of isomorphism has focused on group theoretical methods. On the other hand, one of the current Grohe´s projects funded by the German Research Foundation (DFG): Logik, Struktur und das Graphenisomorphie, uses techniques of modern graph structure theory as well as techniques of logic, more precisely finite model theory, which are known to be closely related to combinatorial approaches to solving the problem of isomorphism.

 

With the kind support of the FWF-funded Doctoral College Logical Methods in Computer Science (LogiCS) and Vienna Center for Logic and Algorithms (VCLA).