Theorem:For any fixed planar graphH, a maximum flow in anH-minor-free graph with n vertices can be computed in O(n) time.

Readers familiar with graph minors and maximum flows may want to try to prove this theorem themselves, before reading the following two-line proof.

Proof:Robertson and Seymour proved that any graph excluding a fixed planar graph as a minor has constant treewidth. Hagerup, Nishimura, Katajainen, and Ragde proved that maximum flows in graphs of constant treewidth can be computed in linear time. □

Sounds pretty cool, right? But now let's fill in some of those constants.

Suppose the graph *H* has *k* vertices. Classical results in graph drawing imply that *H* is a minor of a (2k-1)×(2k-1) grid; any graph that forbids H as a minor also forbids that grid. Robertson and Seymour proved that any graph with no *r*×*r* grid minor has treewidth at most 2^{O(r5)}. Hagerup *et al.* proved that a maximum flow in an *n*-vertex graph *G* can be computed in time 2^{O(t²)} *n*, given a tree decomposition of *G* of width *t*. Finally, an algorithm of Bodlaender computes a tree decomposition of minimum width *t* in 2^{O(t³)}*n* time. As far as I know, all of these upper bounds are the best known for their respective problems.

So the theorem should really be written like this:

Theorem:For any fixed planark-vertex graphH, a maximum flow in ann-vertexH-minor-free graph can be computed in 2^{2O(k5)}ntime.

the problem with the original statement of the theorem is that it doesn't say "linear" in what? So I don't agree that the theorem is useless, but I agree that its misleading as stated.

Posted by: Paul | December 10, 2009 at 08:34 AM

Doesn't "linear time"

alwaysmean "time that grows linearly with the size of the input"? I've changed the wording; hopefully it's unambiguous now.Posted by: JeffE | December 10, 2009 at 08:59 AM

In this case, what is the input to the algorithm? Is it just the minor-free graph, or is it also H? The statement of the theorem (without insight into the proof) makes the reader think that the input includes H, in which case "linear time in the size of the input" is incorrect.

If i understand correctly the proof though, the algorithm's input is just the minor-free graph and |V(H)|, not H itself.

Posted by: Paul | December 11, 2009 at 09:32 AM

I was referring back to the old version of the statement, of course, the way it is now is unambiguous.

Posted by: Paul | December 11, 2009 at 09:34 AM

Hilarious!

Posted by: asarwate | December 12, 2009 at 01:36 PM

Well, this is not totally related, but I would like to point out that using reasonable constants relating the number of edges in a graph to vlogv we get that Dinic's algorithm has runtime V^2log^2V for these graphs in a non-useless way.

Posted by: Abel | December 13, 2009 at 11:18 PM