26
$\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. :)

$\endgroup$
3
  • $\begingroup$ I'm very curious to hear more about this. $\endgroup$ Aug 23 '11 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$ Aug 23 '11 at 14:38
  • 2
    $\begingroup$ So neither of them decided to write it up after more than three years? $\endgroup$ Aug 24 '11 at 3:43
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.

$\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$ Aug 24 '11 at 22:43
  • $\begingroup$ The quadratic time paper was published in 2012: JCTB 102 (2): 424–435, doi.org/10.1016/j.jctb.2011.07.004 $\endgroup$ May 31 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.

$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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