7
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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. $\endgroup$ Commented Feb 19, 2014 at 13:19

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This answer is about minors and not about topological minors, which stand for subdivided copy. $\endgroup$
    – domotorp
    Commented Apr 15 at 8:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.