# 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'm very curious to hear more about this. – Suresh Venkat Aug 23 '11 at 6:37
• 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
• So neither of them decided to write it up after more than three years? – Timothy Sun Aug 24 '11 at 3:43

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.