« How to host SODA outside North America | Main | 2010 CS theory postdocs »

December 10, 2009



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.


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.


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.


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




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.

The comments to this entry are closed.