13.12.15 - 18.12.15, Seminar 15511

The Graph Isomorphism Problem

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.

Motivation

The Graph Isomorphism Problem remains one of the few natural computational problems with unknown complexity status. In very rough terms the problem is to decide whether two given graphs are structurally different or one is just a perturbed variant of the other.

The problem naturally arises when one is faced with the task of classifying relational structures. Having been open and quite prominent for some time now, the Graph Isomorphism Problem is repeatedly attacked with the abundance of algorithmic techniques that have been developed over the decades. While this has not led to a resolution of the problem it has led to applications of techniques developed for the Graph Isomorphism Problem in other areas (such as machine learning and constraint satisfaction problem solving) as well as sparked fascinating concepts in complexity theory, led to a thriving compilation of techniques in algorithmic group theory, the development of software packages (such as canonical labeling tools) and perpetuating effects in algorithmic graph theory in general.

While many other computational problems have a canonical community associated with them, resulting in dedicated conferences, the situation for the isomorphism problem is different. This is due to the fact that the background of people working on the isomorphism problem is quite diverse which leads to infrequent encounters at regular conferences or other events.

This diverse landscape manifests itself for example in the following communities:

  • practitioners that implement software around the Graph Isomorphism Problem yielding widely used packages and libraries
  • logicians approaching the Graph Isomorphism Problem with techniques such as descriptive complexity theory, and using the problem to prove lower bounds in several proof systems
  • algorithmic group theorists that drive the approach to the problem via group theory, yielding to date the best known algorithm with respect to worst-case complexity
  • graph theoristsanalyzing the underlying objects from a structural viewpoint solving ever-increasing subcases of the general problem
  • complexity theorists highlighting the special position the Graph Isomorphism Problem takes in the complexity landscape
  • scientists from the area of combinatorial optimization that apply optimization techniques to isomorphism solving (such as semi-definite programming hierarchies) and conversely use isomorphism tools to speed up optimization procedures
  • researchers that apply isomorphism related techniques in and from other areas such as machine learning

In this seminar we bring together researchers working on these core facets of the Isomorphism Problem. This bridges gaps between theory and practice, by exposing practical bottlenecks to theoreticians on the one hand and encouraging the use of new theoretical techniques in practice on the other hand. It also fosters collaboration among the theorists allowing the combination of orthogonal approaches. This will help to push the boundary of our understanding, bringing us hopefully a step closer to understanding the Graph Isomorphism Problem.

The program will include the following five overview talks on topics of great current interest.

  1. Graph indistinguishability through hierarchies of relaxations [Albert Atserias]
  2. Practical aspects of the graph isomorphism problem [Brendan McKay]
  3. Graph isomorphism: the bottlenecks [Laszlo Babai]
  4. Complexity classes and graph isomorphism [Jacobo Toran]
  5. Parameterizations and the graph isomorphism problem [Pascal Schweitzer]