<p>A recent paper by Isolde Adler1, Frederic Dorn, Fedor V. Fomin, Ignasi Sau and Dimitrios M. Thilikos called <a href="http://www.lirmm.fr/~sau/Pubs/ADF+10b.pdf">Fast Minor Testing in Planar Graphs</a> shows that when looking for a minor $H$ on $h$ vertices in a <em>planar graph</em> $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.</p>

CC BY-SA 3.0
2011-09-01T08:48:22.977Z
2011-09-01T08:48:22.977Z
Bart Jansen
<p>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.</p>
<p>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 &quot;functor
project&quot; 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</p>

CC BY-SA 4.0
2021-05-30T21:34:07.490Z
2021-05-30T21:34:07.490Z
Michael Fellows
<p>There is a preprint by Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed that claims a quadratic time algorithm: "<a href="http://research.nii.ac.jp/~k_keniti/quaddp1.pdf">The disjoint paths problem in quadratic time</a>". 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).</p>

<p>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, <a href="http://dx.doi.org/10.1007/978-3-642-19094-0_2">doi:10.1007/978-3-642-19094-0_2</a>.</p>

<p>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.</p>

CC BY-SA 3.0
2011-08-24T22:43:52.597Z
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
CC BY-SA 4.0
2021-05-31T16:37:47.850Z
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
CC BY-SA 3.0
2011-08-24T21:17:50.570Z
2011-08-24T21:17:50.570Z
David Eppstein
<p>The result by <a href="http://www.sciencedirect.com/science/article/pii/S0095895685710064">Robertson and Seymour</a> 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:</p>

<p>1) It appears that there have been improvements to this algorithm since. What is the best-known algorithm at present?</p>

<p>2a) What do people conjecture to be the optimal bound?</p>

<p><a href="http://epubs.siam.org/sidma/resource/1/sjdmec/v12/i1/p6_s1">Mohar's algorithm for embedding on a fixed surface</a> and <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5438591">Kawarabayashi's algorithm for recognizing $k$-apex graphs</a> decide membership of graphs characterizable by forbidden minors in linear time, motivating the last question:</p>

<p>2b) Is there any reason to suspect that we can do this in linear time?</p>

<p>Of course, if someone already came up with a linear-time algorithm, the last two questions are silly. :)</p>

CC BY-SA 3.0
2011-08-23T06:37:07.347Z
I'm very curious to hear more about this.
Suresh Venkat
CC BY-SA 3.0
2011-08-23T14:38:28.763Z
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](http://blog.computationalcomplexity.org/2008/01/more-on-graph-minors.html), for example.
Robin Kothari
CC BY-SA 3.0
2011-08-24T03:43:23.040Z
So neither of them decided to write it up after more than three years?
Timothy Sun
<reference-request><graph-theory><co.combinatorics><graph-algorithms>
The complexity of determining if a fixed graph is a minor of another
Timothy Sun
# The complexity of determining if a fixed graph is a minor of another

(Asked by: username_0 on 2011-08-23)

The result by [Robertson and Seymour](http://www.sciencedirect.com/science/article/pii/S0095895685710064) 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](http://epubs.siam.org/sidma/resource/1/sjdmec/v12/i1/p6_s1) and [Kawarabayashi's algorithm for recognizing $k$-apex graphs](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5438591) 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. :)

**Tags:** reference-request, graph-theory, co.combinatorics, graph-algorithms
> **Comments:**
> **username_1**: I'm very curious to hear more about this.  
> **username_2**: 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](http://blog.computationalcomplexity.org/2008/01/more-on-graph-minors.html), for example.  
> **username_0**: So neither of them decided to write it up after more than three years?  

---

## 3 answers

### Answer by username_5 on 2011-08-24. Score: 15 | Accepted answer

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](http://research.nii.ac.jp/~k_keniti/quaddp1.pdf)". 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](http://dx.doi.org/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.

> **Comments:**
> **username_0**: 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?  
> **username_5**: The quadratic time paper was published in 2012: JCTB 102 (2): 424–435, https://doi.org/10.1016/j.jctb.2011.07.004  

---

### Answer by username_3 on 2011-09-01. Score: 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](http://www.lirmm.fr/~sau/Pubs/ADF+10b.pdf) 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.


---

### Answer by username_4 on 2021-05-30. Score: 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


---

