27
$\begingroup$

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. :)

Improve this question
$\endgroup$
3
  • $\begingroup$ I'm very curious to hear more about this. $\endgroup$
    – Suresh Venkat
    Aug 23, 2011 at 6:37
  • 11
    $\begingroup$ 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. $\endgroup$
    – Robin Kothari
    Aug 23, 2011 at 14:38
  • 2
    $\begingroup$ So neither of them decided to write it up after more than three years? $\endgroup$
    – Timothy Sun
    Aug 24, 2011 at 3:43

3 Answers 3

Reset to default
15
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Timothy Sun
    Aug 24, 2011 at 22:43
  • 1
    $\begingroup$ The quadratic time paper was published in 2012: JCTB 102 (2): 424–435, doi.org/10.1016/j.jctb.2011.07.004 $\endgroup$
    – David Eppstein
    May 31, 2021 at 16:37
7
$\begingroup$

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.

Improve this answer
$\endgroup$
6
$\begingroup$

There are old results showing that linear minor testing is possible for some specific graphs H, basically by looking at back-edge patterns in depth-first search, with significant effort for each H, and only a few are known. But, it is kind of like having linear FPT for k up to 4, which can make one suspicious.

Recently discussed this issue with Rod. My own feeling is that even topological minor testing parameterized by H is / will be ultimately linear FPT by a "functor project" sort of approach. Little is yet written about this (a tiny bit in the Bodlaender festschrift) but a very active project. michael.fellows@uib.no

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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