The Graph Isomorphism Problem

 

Lecture in the summer term 2017

 

Content

The question of whether there is a polynomial time algorithm deciding whether two graphs are isomorphic, known as the "graph isomorphism problem", has been 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. Remarkably, the problem has first been studied by chemists in the 1950s. Even though the problem is still open, researchers have obtained a number of substantial partial results. These results rely on a variety techniques from different branches of theoretical computer science and discrete mathematics. In this class, we will cover the highlights of forty years of research on the graph isomorphism problem, starting with early results from the 1970s to current research. Each of the results will be embedded in an introduction to the specific techniques and the context.

Thus on the one hand the class will give an in-depth treatment of a current research question in theoretical computer science. On the other hand, it spans a wide range of topics in algorithms, complexity theory, logic, graph theory, and group theory and conveys selective, yet deep insights into all these areas and the interaction among the areas.

Prerequisites

Prerequisite for this course is a solid foundation in theoretical computer science and a successful completion of the required courses for the Bachelor in Computer Science such as "Data Structures and Algorithms" and "Computability and Complexity".

 

Organization

The course will be held in english.

Time and Place

Monday, 4:15pm - 5:45pm in 2350|009 (AH I)
Wednesday, 10:15am - 11:45am in 2356|055 (5055)

Lecturer

Martin Grohe

 

Exercises

There will be weekly exercise sets. Completing these successfully, reaching at least 50% of possible points, is necessary for admittance to the examination.

The solutions of the exercises will be presented on Monday, 12:15am - 13:45am in 2356|052 (5052).

Oral Exam

There will be oral exams. The exact modalities of the exams will be announced later.