The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:

1) It appears that there have been improvements to this algorithm since. What is the best-known algorithm at present?

2a) What do people conjecture to be the optimal bound?

Mohar's algorithm for embedding on a fixed surface and Kawarabayashi's algorithm for recognizing $k$-apex graphs decide membership of graphs characterizable by forbidden minors in linear time, motivating the last question:

2b) Is there any reason to suspect that we can do this in linear time?

Of course, if someone already came up with a linear-time algorithm, the last two questions are silly. :)

  • I'm very curious to hear more about this. – Suresh Venkat Aug 23 '11 at 6:37
  • 10
    I have heard that Bruce Reed and Ken-ichi Kawarabayashi have an $O(n \log n)$ time algorithm, but it hasn't been written up. This claim appears here, for example. – Robin Kothari Aug 23 '11 at 14:38
  • 2
    So neither of them decided to write it up after more than three years? – Timothy Sun Aug 24 '11 at 3:43
up vote 13 down vote accepted

There is a preprint by Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed that claims a quadratic time algorithm: "The disjoint paths problem in quadratic time". It is formatted as a conference submission rather than a journal paper so I'm not sure it's possible to verify the details, though (I haven't really tried, myself).

A very recent survey by Kawarabayashi cites this as the best known result for the closely related disjoint paths problem: Ken-ichi Kawarabayashi (2011), "The Disjoint Paths Problem: Algorithm and Structure", WALCOM: Algorithms and Computation, LNCS 6552, pp. 2–7, doi:10.1007/978-3-642-19094-0_2.

I don't know whether this means that the $O(n\log n)$ claim in Kothari's comment is vapor or whether it means that it's still at an earlier stage of being written up.

  • Thanks! But if the $O(n\log n)$ claim was true, wouldn't he have said something like "in preparation," seeing that this is in fact his own result? – Timothy Sun Aug 24 '11 at 22:43

A recent paper by Isolde Adler1, Frederic Dorn, Fedor V. Fomin, Ignasi Sau and Dimitrios M. Thilikos called Fast Minor Testing in Planar Graphs shows that when looking for a minor $H$ on $h$ vertices in a planar graph $G$, this can be done in $2^{O(h)} n + O(n^2 \log n)$ time. While the dependence on $n$ is not as good as the one mentioned in the answer by David, the dependency on $h$ of this work is far superior.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.