<p>The general problem when $H$ is not fixed is NP-hard: Take $H$ to be a cycle of length $|V(G)|$ and it amounts to testing whether $G$ is hamiltonian.</p>

<p>I think that the state of the art on this is the FPT algorithm of 
<a href="http://www.cs.bme.hu/~dmarx/papers/grohe-stoc2011-topminor.pdf" rel="nofollow">Grohe, Kawarabayashi, Marx and Wollan</a>. The dependency on $G$ is cubic, but the one on $H$ seems impractical, since it relies quite heavily on the Robertson-Seymour theory.</p>

CC BY-SA 3.0
2014-02-19T13:22:22.310Z
2014-02-19T13:27:49.377Z
2014-02-19T13:27:49.377Z
Arnaud
<p>I think the main reason for most literature topics focusing on a fixed small is the <a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow">Robertson–Seymour theorem</a>. </p>

<blockquote>
  <p>If F is a minor-closed family, then let S be the set of graphs that
  are not in F (the complement of F). According to the Robertson–Seymour
  theorem, there exists a finite set H of minimal elements in S.</p>
</blockquote>

<p>So most of the algorithms in literature involving finding minors in a graph somehow make the family of forbidden graphs finite so that the main problem can be solved efficiently.</p>

<p>So, in general when $H$ is not fixed it is hard to do better than a exponential algorithm. But some still special cases like "<a href="http://dl.acm.org/citation.cfm?id=982792.982920" rel="nofollow">Hole and Antihole Detection in Graphs</a>" by Stavros D. Nikolopoulos and Leonidas Palios might be intersting to you.  </p>

CC BY-SA 4.0
2024-04-15T08:33:34.267Z
This answer is about minors and not about topological minors, which stand for subdivided copy.
domotorp
CC BY-SA 3.0
2014-02-19T18:04:30.777Z
2014-02-19T18:04:30.777Z
Dibyayan
<p>I am trying to find about algorithms that, given graph $H, G$, determine if $H$ is a topological minor of $G$ (and if so, exhibit this explicitly). Most of the literature on this topic seems to be focused on the case when $H$ is a fixed small graph while $G$ goes to infinity --- e.g. testing if $G$ is planar. What are the algorithms when $H$ and $G$ are comparable in size? </p>

<p>If this problem requires exponential time, I would still be interested in the best algorithms and/or real implementations</p>

CC BY-SA 3.0
2014-02-19T13:19:21.253Z
I don't know what the best known algorithm is, but the problem is NP-complete since Hamiltonian path is a special case of this problem. So the best known algorithm must be exponential time.
Robin Kothari
<graph-algorithms>
Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?
David Harris
# Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?

(Asked by: username_0 on 2014-02-19)

I am trying to find about algorithms that, given graph $H, G$, determine if $H$ is a topological minor of $G$ (and if so, exhibit this explicitly). Most of the literature on this topic seems to be focused on the case when $H$ is a fixed small graph while $G$ goes to infinity --- e.g. testing if $G$ is planar. What are the algorithms when $H$ and $G$ are comparable in size?

If this problem requires exponential time, I would still be interested in the best algorithms and/or real implementations

**Tags:** graph-algorithms
> **Comments:**
> **username_1**: I don't know what the best known algorithm is, but the problem is NP-complete since Hamiltonian path is a special case of this problem. So the best known algorithm must be exponential time.  

---

## 2 answers

### Answer by username_2 on 2014-02-19. Score: 4 | Accepted answer

The general problem when $H$ is not fixed is NP-hard: Take $H$ to be a cycle of length $|V(G)|$ and it amounts to testing whether $G$ is hamiltonian.

I think that the state of the art on this is the FPT algorithm of
[Grohe, Kawarabayashi, Marx and Wollan](http://www.cs.bme.hu/~dmarx/papers/grohe-stoc2011-topminor.pdf). The dependency on $G$ is cubic, but the one on $H$ seems impractical, since it relies quite heavily on the Robertson-Seymour theory.


---

### Answer by username_3 on 2014-02-19. Score: 3

I think the main reason for most literature topics focusing on a fixed small is the [Robertson–Seymour theorem](http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem).

> If F is a minor-closed family, then let S be the set of graphs that
> are not in F (the complement of F). According to the Robertson–Seymour
> theorem, there exists a finite set H of minimal elements in S.

So most of the algorithms in literature involving finding minors in a graph somehow make the family of forbidden graphs finite so that the main problem can be solved efficiently.

So, in general when $H$ is not fixed it is hard to do better than a exponential algorithm. But some still special cases like "[Hole and Antihole Detection in Graphs](http://dl.acm.org/citation.cfm?id=982792.982920)" by Stavros D. Nikolopoulos and Leonidas Palios might be intersting to you.

> **Comments:**
> **username_4**: This answer is about minors and not about topological minors, which stand for subdivided copy.  

---

