- Exercise set 8 can be found here.
- From now on, the tutorials will start at 15:00 (instead of 15:15).
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.
The following list shows my current idea of topics covered in the
lecture. It may change during
the semester. I will try to keep it up to date.
- Colour Refinement
- Individualisation-Refinement Algorithms
- Planar Graphs and Other Special Graph Classes
- The Weisfeiler-Lehman Algorithm
- Group Theoretic Algorithms (still incomplete)
- Spectral Techniques
Brief notes about every lecture can be found here (after the lectures).
- Time and location
- Tuesdays 13:15-14:45 and Thursdays 11:15-12:45,
Schrödinger Zentrum (Rudower Chaussee 26),
Prof. Dr. Martin Grohe
- Office hours: Thursdays 15:00 - 16:00
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),
Dr. Paul Bonsma
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.
Exercise set 1 (to be handed in on April 24).
Exercise set 2 (to be handed in on May 8).
Exercise set 3 (to be handed in on May 15).
Exercise set 4 (to be handed in on May 29).
Exercise set 5 (to be handed in on June 12).
Exercise set 6 (to be handed in on June 19).
Exercise set 7 (to be handed in on July 3).
Exercise set 8 (to be handed in on July 10).
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.
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.
- Babai, L.
Monte-Carlo Algorithms in Graph Isomorphism Testing
Université de Montréal Technical Report, DMS, Citeseer, 1979
- Babai, L., Erdös, P. and Selkow, S.
Random Graph Isomorphism
SIAM Journal on Computing, 1980, Vol. 9, pp. 628-635
- Babai, L. and Luks, E.
Canonical Labeling of Graphs
Proceedings of the 15th ACM Symposium on Theory of Computing
1983, pp. 171-183
- Bodlaender, H.
Polynomial Algorithms for Graph Isomorphism and Chromatic Index on Partial k-Trees
Journal of Algorithms, 1990, Vol. 11, pp. 631-643
- Boppana, R., Hastad, J. and Zachos, S.
Does co-NP Have Short Interactive Proofs?
Information Processing Letters, 1987, Vol. 25, pp. 127-132
- 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
- Grohe, M.
From Polynomial Time Queries to Graph Structure Theory
Communications of the ACM, 2011, Vol. 54(6), pp. 104-112
- Grohe, M. and Marx, D.
Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
- 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
- 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
- Köbler, J., Torán, J. and Schöning, U.
The Graph Isomorphism Problem: Its Structural Complexity
- 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
- Mathon, R.
A Note on the Graph Isomorphism Counting Problem.
Information Processing Letters, 1979, Vol. 8(3), pp. 131-132
- Schöning, U.
Graph Isomorphism is in the Low Hierarchy
Journal of Computer and System Sciences, 1988, Vol. 37, pp. 312-323
Last modified: Tue July 3 19:05 2012