# Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?

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

• 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. Commented Feb 19, 2014 at 13:19

## 2 Answers

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. The dependency on $G$ is cubic, but the one on $H$ seems impractical, since it relies quite heavily on the Robertson-Seymour theory.

I think the main reason for most literature topics focusing on a fixed small is the Robertson–Seymour 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" by Stavros D. Nikolopoulos and Leonidas Palios might be intersting to you.

• This answer is about minors and not about topological minors, which stand for subdivided copy. Commented Apr 15 at 8:33