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 
We assume
- In round one, breaker removes any
edges from
- In round two, maker can add any
edges to
Maker wins if the final graph has the property 
As a simple example, let the graph be a cycle and the property be the graph is connected. Clearly, if breaker can remove 
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 
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 
- 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
vertices.
The algorithm’s running time is cubic, but the constant in the O-notation depends super-exponentially on the size of the graph
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
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 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.
Open Problems
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 
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.
Trackbacks
- Issues In The Proof That P≠NP « Gödel’s Lost Letter and P=NP
- Complexity on Forbidden-Minor Planets? « Gödel’s Lost Letter and P=NP
- The Travelling Salesman’s Power « Gödel’s Lost Letter and P=NP
- In Praise Of P=NP Proofs | Gödel's Lost Letter and P=NP
- We Say Branches And You Say Choices | Gödel's Lost Letter and P=NP
Wow, Google already catalogued this post as top hit for a query I made looking for an answer to a query I had about unordered structures, in the 2 hours since sending you the e-mail before dinner! A guess of getting back your query as the answer… I was curious about whether a polynomial-time logic capturing unordered structures like graphs must entail a poly-time isomorphism test, perhaps depending on fine details of the logics and/or structures. An earlier, very accessible reference by Grohe, http://www2.informatik.hu-berlin.de/~grohe/pub/gro08b.pdf, tells me no, after digesting the details of its three flavors of “condition C2”.
The “key” question is still open, and Grohe relates that Yuri Gurevich conjectured “no”. The notions are framed in a way that since Fagin’s Theorem gives a logic capturing NP without reference to order, a “no” answer implies NP != P. The manner by which Grohe derives an isomorphism test for any minor-closed class of graphs, by an algorithm whose code doesn’t reference the logical characterization but whose proof of poly-time termination does, seems strangely indirect. Still looking at it…
Wait, am I missing something or is the part about bounded degree not true? It seems to me that one can take a graph of max degree 3 (say a tree, even) and contract edges to get arbitrarily large degrees.
I don’t understand the part about a logic capturing P-time. Does predicative recursion (Cook and Bellantoni) do that? See: http://www.cs.toronto.edu/~sacook/homepage/ptime.pdf
That’s a more algebraic kind of logical system, where one generates polynomial-time computable functions f by recursion. In that kind of system, the logic may be involved in proving that f is total, via proving that the (or some) program representing f halts for all inputs [within the specified time].
The system in Grohe’s paper operates by defining rather than proving. That is, one generates a formula Q(u,v,w,…) where u,v,w… refer to vertices of graphs. The body of the formula may reference an abstract edge relation E(u,v). An example of a formula—actually a sentence since all variables are quantified—is:
Now given a sentence s, we can define L(s) to be the collection of all graphs G such that s becomes true when u,v,w… range over nodes in V(G), and “E” is the relation E(G). Above, such graphs are exactly those that have a [directed] triangle. Note that if I had been able to refer to an ordering of nodes, then I could have replaced the
part by 
. However, this would only work if the vertices were labeled so that the triangle has two "ascending" edges. Hence it would not be defining an order-independent property of graphs. If I made it 
then it would be OK, since even though it references an ordering, it would hold for all graphs with a triangle regardless of ordering. This is because a triangle would either have two consecutive ascending or two consecutive descending edges, under any ordering. Of course “G has a triangle” is polynomial-time decidable—in fact it belongs to DLOGTIME-uniform AC^0, and that class is captured by first-order formulas (with order). This finally expresses some of the subtlety involved in these descriptive-complexity questions.
Lines 9-10 from bottom should read—ah, my original LaTeX looks right, so what happened? “If I made it
…”
Still wrong—weird. Non-LaTeX, it was (u less-than v & v less-than w) OR (u gt-than v & v gt-than w). Maybe a literal less-than symbol looked like HTML for a link, despite being inside the LaTeX escape.
I missed the bounded-degree thing too. Edge-contraction can increase degree. Of interest in what Grohe writes is that Pomarenko’s 1988 isomorphism-test for graphs with excluded minors built on the earlier bounded-degree work.
HTML-code for (u less-than v & v less-than w) OR (u gt-than v & v gt-than w)
I edited the following LaTeX-code in my auxiliary blog:
The HTML-code, in which I insert spaces for displaying here, is:
$ l a t e x ( u & l t ; v \ w e d g e v & l t ; w ) \ v e e ( u & g t ; v \ w e d g e v & g t ; w ) $
The “less than” and “greater than” signs which sometimes cause display troubles here (in this moment your formula does not parse) are, of course, & l t ; and & g t ;
Dr. Tavares: Thanks! I’ll remember various ampersand-escapes, nice to know that the “latex” function understands them.
The bounded degree result does not follow from Grohe’s result. A bounded degree expander can have a poly-sized clique as a minor.
My error…
You are both correct…will update post.
Again very sorry for making such a stupid error.
Well, the most famous lengthy graph minor-driven result is probably the four color theorem (I am thinking of the minimal counter-examples). I would think that a reasonable explanation for why graph minor results are so long would also suggest why the quest for a more elegant proof of the four color theorem is foolish. Being an optimist, I would rather hang on to the idea that there is some amazing, elegant, and yet to be discovered structure of graphs.
If I understand correctly, then the logic that is used to capture PTIME on H-minor-free graphs is defined such that for all properties expressible by the logic, you can construct a polynomial-time algorithm for recognizing graphs with that property. Can anyone tell me how the running time of the polynomial-time algorithm is affected by the formula size and the graph size?
If the running time would be f(k) p(n) where f is an arbitrary function of the formula size and p is a polynomial only depending on the graph size n, then Grohe’s result could be used to classify graph properties whose recognition problem is fixed-parameter tractable on H-minor-free graphs, similar to what Courcelle’s theorem does for bounded-treewidth graphs.
I guess that the running time will be exponential on k (somethink like n^{f(k)}) where k depends on the formula and f a tower of exponents. In fact, bounded twd classes are minor-free and there are some problems which are in PTIME but not fpt. Otherwise, he will also claim that W-hierarchy collapes to fpt.
Thanks for the wonderful post. Regarding the ‘maker’ and ‘breaker’ game, in my PhD dissertation, which I just defended ( http://jsaia.wordpress.com/ ) we have proposed algorithms for self-healing. Our setting bears some resemblance to the game you describe. Our motivation is to give distributed algorithms in reconfigurable networks like P2P networks. Our game is played over multiple rounds: in each round the adversary (‘breaker’) gets to remove a node (and all the incident edges) and the algorithm (“maker’) can fix the graph by adding some edges back. Moreover, the edges can only be between neighbors or close-by nodes. Also, each node corresponds to a processor/computer/entity in the network and the algorithms have to be fully distributed. We don’t have direct constraints on the number of edges added back but the properties we maintain force a low number of new edges (now that you raise the question, It will be interesting to think if we always add less edges than the degree of deleted node!). We also have insertions happening to the graph.
Here are some links:
– Our latest algorithm ForgivingGraph (PODC 2009, http://portal.acm.org/citation.cfm?id=1582740) maintains connectivity, low degree increase and low stretch.
– ForgivingTree (PODC 2008, http://portal.acm.org/citation.cfm?id=1400779) maintains connectivity, very low degree increase and low diameter.
Yuster and Zwick have managed to speed-up significantly an algorithm for finding a maximum matching in graphs with excluded minor.
http://research.haifa.ac.il/~raphy/papers/minor.ps — here is the link to this paper
Not about minors but found today interesting paper “Polynomial Time Algorithm for Graph Isomorphism Testing”, Michael I. Trofimov http://arxiv.org/abs/1004.1808 . This is O(n^5) algorithm. It looks like quite different approach, but can work for some not so large graphs (beyond 200 vertex, high precision floating point calculations are needed, but authors claims that grow of floats doesn’t leads to explosion of complexity). Any way nice borrow of ideas from other fields of science.