http://www.dagstuhl.de/15511

13. – 18. Dezember 2015, Dagstuhl Seminar 15511

The Graph Isomorphism Problem

Organisatoren

Laszlo Babai (University of Chicago, US)
Anuj Dawar (University of Cambridge, GB)
Pascal Schweitzer (RWTH Aachen, DE)
Jacobo Torán (Universität Ulm, DE)


1 / 3 >

Auskunft zu diesem Dagstuhl Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl Report, Volume 5, Issue 12 Dagstuhl Report
Motivationstext
Teilnehmerliste
Gemeinsame Dokumente
Dagstuhl's Impact: Dokumente verfügbar

Summary

The Graph Isomorphism Problem remains one of the two unresolved computational problems from Garey and Johnson's list dating back to 1979 of problems with unknown complexity status. In very rough terms the problems asks 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 (e.g., chemical molecules, websites and links, road networks).

While the Graph Isomorphism Problem was intensively studied from the point of view of computational complexity in the 1980s and early 1990s, in later years progress became slow and interest in the problem stalled. However, recent years have seen the emergence of a variety of results related to graph isomorphism in a number of research areas including algorithmic group theory, finite model theory, combinatorial optimization and parameterized algorithms, not to mention graph theory itself. Indeed, having been open and quite prominent for such a long time, 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 resolution of the problem, it has led to applications of methods originally developed for the Graph Isomorphism Problem in other areas (such as machine learning and constraint satisfaction problem solving). It has also 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 a lot of other computational problems have a specific 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. Moreover, there is a big gap between theory and practice, a phenomenon verbalized by Brendan McKay as two distinct galaxies with very few stars in between them. Indeed, the algorithms that are asymptotically fastest in theory are very different to the ones that prove to be the fastest in practical implementations. The original motivation of the seminar was to bring together researchers working on the many topics closely related to the Isomorphism Problem to foster their collaboration.

However, the face of the seminar was to change, as one of the organizers (László Babai) published a proof on the arXiv (http://arxiv.org/abs/1512.03547) on the night before the seminar that shows that graph isomorphism can be solved in quasi-polynomial time (see the abstract to the talk below). This is the first improvement over the moderately exponential algorithm for general graphs by Luks from 1983. Babai gave three intense blackboard presentations each with a duration of two hours on the new quasi-polynomial time algorithm. Apart from the presentations, there were a number of excellent talks including expository surveys on recent advances in a variety of aspects of the Graph Isomorphism Problem as detailed below.

Overall a memorable event, we hope that the seminar has encouraged future collaboration across the different areas which eventually brings us closer to the theoretical and practical resolution of the problem.

License
  Creative Commons BY 3.0 Unported license
  Laszlo Babai and Anuj Dawar and Pascal Schweitzer and Jacobo Torán

Classification

  • Data Structures / Algorithms / Complexity
  • Software Engineering
  • Verification / Logic

Keywords

  • Graph Isomorphism
  • Canonical Forms
  • Computational Group Theory
  • Complexity
  • Lift-and-Project Hierarchies

Buchausstellung

Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.