Favorite useless theorem #1

Theorem: For any fixed planar graph H, a maximum flow in an H-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 planar k-vertex graph H, a maximum flow in an n-vertex H-minor-free graph can be computed in 2^2O(k5)n time.

Comments

[Paul]

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.

[JeffE]

Doesn't "linear time" always mean "time that grows linearly with the size of the input"? I've changed the wording; hopefully it's unambiguous now.

[Paul]

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.

[Paul]

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

[asarwate]

Hilarious!

[Abel]

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.