# The complexity of determining if a fixed graph is a minor of another

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 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. Aug 23 '11 at 14:38
• So neither of them decided to write it up after more than three years? Aug 24 '11 at 3:43

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

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.

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