Logic in Computer Science Prof. Dr. Martin Grohe

News

• Exercise set 8 can be found here.
  
• From now on, the tutorials will start at 15:00 (instead of 15:15).

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.

The lectures will be given in English.

Contents

0. Notation
1. Introduction
2. Colour Refinement
3. Individualisation-Refinement Algorithms
4. Planar Graphs and Other Special Graph Classes
5. The Weisfeiler-Lehman Algorithm
6. Group Theoretic Algorithms (still incomplete)
7. Spectral Techniques
8. Complexity
9. Bibliography

Lecture Log

Brief notes about every lecture can be found here (after the lectures).

Lectures

Time and location

Tuesdays 13:15-14:45 and Thursdays 11:15-12:45, Schrödinger Zentrum (Rudower Chaussee 26), room 1'307

 

Lecturer

Prof. Dr. Martin Grohe

Office hours: Thursdays 15:00 - 16:00

Tutorials

In addition to the lectures there will be 2 hour tutorials.

Time and location

Tuesdays, 15:15-16:45,Schrödinger Zentrum (Rudower Chaussee 26), room 1'307

 

Tutor

Dr. Paul Bonsma

Exercises

There will be weekly exercise sets. Completing these successfully (at least 40% of all points) is necessary for receiving the course credit ("Schein") and admittance to the examination.

1. Exercise set 1 (to be handed in on April 24).
2. Exercise set 2 (to be handed in on May 8).
3. Exercise set 3 (to be handed in on May 15).
4. Exercise set 4 (to be handed in on May 29).
5. Exercise set 5 (to be handed in on June 12).
   
6. Exercise set 6 (to be handed in on June 19).
   
7. Exercise set 7 (to be handed in on July 3).
   
8. Exercise set 8 (to be handed in on July 10).
   

Examination

In the beginning of the semester break there will be oral examinations. For admittance to these examinations at least 40% of the exercise points are necessary.

References

There are no textbooks on the material covered in this class. Below is a selection of research papers and monographs on various topics related to the class.

1. Babai, L. Monte-Carlo Algorithms in Graph Isomorphism Testing Université de Montréal Technical Report, DMS, Citeseer, 1979
2. Babai, L., Erdös, P. and Selkow, S. Random Graph Isomorphism SIAM Journal on Computing, 1980, Vol. 9, pp. 628-635
3. Babai, L. and Luks, E. Canonical Labeling of Graphs Proceedings of the 15th ACM Symposium on Theory of Computing 1983, pp. 171-183
4. Bodlaender, H. Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees Journal of Algorithms, 1990, Vol. 11, pp. 631-643
5. Boppana, R., Hastad, J. and Zachos, S. Does co-NP Have Short Interactive Proofs? Information Processing Letters, 1987, Vol. 25, pp. 127-132
6. Cai, J., Fürer, M. and Immerman, N. An Optimal Lower Bound on the Number of Variables for Graph Identification Combinatorica, 1992, Vol. 12, pp. 389-410
7. Grohe, M. From Polynomial Time Queries to Graph Structure Theory Communications of the ACM, 2011, Vol. 54(6), pp. 104-112
8. Grohe, M. and Marx, D. Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs 2012
9. Hopcroft, J. and Wong, J. Linear Time Algorithm for Isomorphism of Planar Graphs Proceedings of the 6th ACM Symposium on Theory of Computing 1974, pp. 172-184
10. Hopcroft, J.E. and Tarjan, R. A Vlog V Algorithm for Isomorphism of Triconnected Planar Graphs Journal of Computer and System Sciences, 1973, Vol. 7, pp. 323-331
11. Köbler, J., Torán, J. and Schöning, U. The Graph Isomorphism Problem: Its Structural Complexity Birkhäuser, 1993
12. Luks, E. Isomorphism of Graphs of Bounded Valance Can Be Tested in Polynomial Time Journal of Computer and System Sciences, 1982, Vol. 25, pp. 42-65
13. Mathon, R. A Note on the Graph Isomorphism Counting Problem. Information Processing Letters, 1979, Vol. 8(3), pp. 131-132
14. Schöning, U. Graph Isomorphism is in the Low Hierarchy Journal of Computer and System Sciences, 1988, Vol. 37, pp. 312-323