Graph Isomorphism and Graph Minors
Graph isomorphism and the theory of excluded graph minors
Paul Seymour is one of the greatest graph theorists in the world, who is perhaps best known for famous work with Neil Robertson on graph minors. In addition, Paul has worked on and solved numerous other famous graph theory problems.
Today I plan on talking about a recent result on graph minors by Martin Grohe—who builds on Robertson-Seymour’s work. I also want to discuss a bit why the proofs of these theorems are so long.
I almost wrote a paper with Paul Seymour once: somehow we never got past some initial discussions. Oh well.
The problem Paul and I considered was a game played on an undirected graph by two players: we called them breaker and maker. Let be any polynomial time computable monotone graph property. For example, could be: the graph is connected, the graph has two edge disjoint spanning trees, or the graph has two disjoint paths from a special vertex to another special vertex .
We assume is true. The game is played in two rounds:
- In round one, breaker removes any edges from .
- In round two, maker can add any edges to —maker is not restricted to just replacing removed edges.
Maker wins if the final graph has the property , and breaker wins if it does not. Of course we assumed : otherwise, the game would be trivial, since maker would just replace all the deleted edges.
As a simple example, let the graph be a cycle and the property be the graph is connected. Clearly, if breaker can remove edges, maker wins if he can add edge; if breaker can remove edges, then he wins if maker can only add edge.
Paul and I, really Paul, could show there were polynomial time algorithms to decide who won this game for a variety of simple properties and for small values of . He is beyond impressive for understanding questions like these—I played a pretty small role.
We were interested in the game, since we thought of “breaker” as destroying part of a telecom network, for example, and “maker” then had to quickly repair edges to restore a property. I still like the general class of these problems, but we never did write down the details. Let me know if this is all known today.
The Result of Grohe
The central idea Martin’s work is based on is the notion of graph minor. A graph is a minor of provided is isomorphic to a subgraph of obtained by
- contracting edges,
- deleting edges, and/or
- deleting isolated vertices.
The concept of minor has some beautiful properties—many have been discovered and then proved by Robertson and Seymour. For example,
Theorem: For a fixed graph , there is an algorithm with running time for testing whether or not is a minor of a given graph with vertices.
The algorithm’s running time is cubic, but the constant in the O-notation depends super-exponentially on the size of the graph . Note, this must be true: if it was only polynomial in the size of , then one could solve the Hamiltonian Cycle problem in polynomial time.
Martin Grohe is an expert on graph minors, and has an important paper in the upcoming LICS conference—Logic in Computer Science. I thank Luca Aceto for pointing out the paper: it is discussed on his interesting blog. Martin’s paper is titled: Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors.
This is what Luca has to say about the paper:
“For an interested, but not very knowledgeable, observer like me, one of the most interesting looking papers that have been selected for the conference seems to be yet another seminal contribution by Martin Grohe.”
Actually, it seems like an amazing result to me. The detailed proof of Martin’s theorem will eventually be well over 200 pages—more on the length of the proof later.
One consequence of Martin’s powerful work is:
Theorem: Consider the family of all graphs without as a minor. Then, there is a polynomial time algorithm for graph isomorphism for this family of graphs.
This is a vast generalization of the following classic result: graph isomorphism on planar graphs is in polynomial time.
It further re-proves Eugene Luks’ famous theorem on graph isomorphism for graphs with bounded degrees. Note, the family of all graphs with degree at most is covered by Martin’s theorem: the graph is just a star with points. Another cool point about Martin’s theorem is he does not rely on the deep structure of finite groups as Luks’ does. My error: the following graph has a degree four minor, but the original had degree at most three: (dotted are deleted and gray is contracted)
Fixed-point Logic with Counting
Grohe actually proves fixed-point logic with counting (FP+C) captures polynomial time over all classes of graphs with excluded minors. What does this mean? He shows for families of graphs without a given minor(s) there is a nice definition of polynomial algorithms: polynomial time equals what can be defined by a certain logic. As Ken Regan says the key is:
No one had provided a logic over unordered vertex
labels which captures polynomial-time decidability on graphs.
This is what Martin does for minor excluded graphs.
One of the major quests, in an attempt to better understand polynomial time, is to discover more “natural” definitions of polynomial time. The usual definition of polynomial time is clear, but it is not easy to work with—especially for negative results. The hope is by replacing Turing machine definitions by logical ones, perhaps more progress can be made.
This program has been pushed by many top researchers over the years, and I will have to devote a whole discussion to it in the future. There are many beautiful results by Jin-Yi Cai, Martin Fürer, Neil Immerman, Moshe Vardi, and many others. Cai, Fürer, and Immerman showed FP+C does not capture all of polynomial time on any graph, for instance. Note, this beautiful theorem is the exact opposite of Martin’s theorem.
Why Are Minor Results so Major?
An interesting question is why are proofs of the results on minor theorems so long? I do not claim to understand the reason, but I have a hypothesis. The obvious hypothesis is the proofs require many cases to be considered. This seems correct, but is not completely satisfying.
There should be a deeper reason why the proofs are so long. Perhaps there is some connection to the classification of simple groups? The reason I raise this is Grohe’s theorem, unlike Luks’, does not need the deep structure of finite groups. Instead, Martin relies on the Robertson-Seymour approach and shows there is a structure theorem for families of minor-excluded graphs. The problem, in my opinion, is that these structural theorems are not trivial even to state. One reason for this may be that graphs are far less constrained than algebraic objects like groups. In any event the theorems are truly impressive.
One obvious open problem is to use Martin’s ideas to improve our understanding of graph isomorphism in general. Can we use his theorem to prove a better bound than is currently known? Can we get a polynomial time graph isomorphism algorithm for graphs whose degree is where is a very slow growing function? I think this could be possible, but I am not an expert in this area.
P.S. Sorry for the error that I made in commenting on Grohe’s theorem. And thanks for several comments that quickly pointed it out.