Logic and
Theory of
Discrete Systems

Informatik 7

The Graph Isomorphism Problem

Lecture Course, SS 2017

Introduction

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.

Prerequisits

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.

Organisation

Lectures

Monday, 16:15 - 17:45 in room AH I

Wednesday, 10:15 - 11:45 in room 5055

Instructor: Martin Grohe

Tutorials

Monday, 12:15 - 13:45 in room 5052

Instructor: Daniel Neuen

Exams

The exact modalities will be announced later.

 L2P

All course materials will be published in l2p (registration via campus).

FaLang translation system by Faboba