27

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

Kaveh
  • 21,577
  • 8
  • 82
  • 183
Timothy Sun
  • 779
  • 5
  • 12

3 Answers3

15

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • 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
  • 1
    The quadratic time paper was published in 2012: JCTB 102 (2): 424–435, https://doi.org/10.1016/j.jctb.2011.07.004 – David Eppstein May 31 '21 at 16:37
7

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.

Bart Jansen
  • 5,265
  • 21
  • 39
6

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

Michael Fellows
  • 61
  • 1
  • 1