<p>The algorithm is described in the proof of Theorem 9. For every proper minor closed class $\mathcal{F}$ and every planar graph $H$ there is a constant $c(\mathcal{F}, H)$ such that if the tree-width of $G\in\mathcal{F}$ is at least $c$, then the answer is positive. Furthermore, the property of containing $H$ as an induced minor is an MSO definable property (and the length of the formula depends on $H$ only). Hence you first check whether the tree-depth of $G$ is smaller than $c$ and compute a tree-decomposition (e.g. by Bodlaender's algorithm). If so, you take an MSO model-checker and check whether $H$ is an induced minor of $G$ by testing whether $G$ satisfies the appropriate formula. If not, you simply answer yes. </p>

<p>Note though that the constant $c$ depends on the class $\mathcal{F}$ and if you don't have an explicit list of excluded minors, there might be no constructive way to find them. You cannot just take a bipartite graph and apply the theorem. The graph must be from some class $\mathcal{F}$ with the above properties. </p>

CC BY-SA 3.0
2013-09-28T21:51:55.857Z
2013-09-28T21:51:55.857Z
Sebastian Siebertz
<p>In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fixed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph class and H is a planar graph.</p>

<p>However, My failure to find a specific algorithm led me to ask the following question.</p>

<blockquote>
  <p>If G is a bipartite graph , and H is a tree then is there any polynomial time algorithm to
  find if H is contained in G using only vertex deletion and edge contraction as the graph 
  operations.</p>
</blockquote>

<graph-theory><graph-algorithms><graph-minor>
H-induced Containment problem
Dibyayan
# H-induced Containment problem

(Asked by: username_0 on 2013-09-08)

In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fixed parameter tractable in |VH| if G belongs to any non-trivial minor-closed graph class and H is a planar graph.

However, My failure to find a specific algorithm led me to ask the following question.

> If G is a bipartite graph , and H is a tree then is there any polynomial time algorithm to
> find if H is contained in G using only vertex deletion and edge contraction as the graph
> operations.

**Tags:** graph-theory, graph-algorithms, graph-minor


---

## 1 answers

### Answer by username_1 on 2013-09-28. Score: 4 | Accepted answer

The algorithm is described in the proof of Theorem 9. For every proper minor closed class $\mathcal{F}$ and every planar graph $H$ there is a constant $c(\mathcal{F}, H)$ such that if the tree-width of $G\in\mathcal{F}$ is at least $c$, then the answer is positive. Furthermore, the property of containing $H$ as an induced minor is an MSO definable property (and the length of the formula depends on $H$ only). Hence you first check whether the tree-depth of $G$ is smaller than $c$ and compute a tree-decomposition (e.g. by Bodlaender's algorithm). If so, you take an MSO model-checker and check whether $H$ is an induced minor of $G$ by testing whether $G$ satisfies the appropriate formula. If not, you simply answer yes.

Note though that the constant $c$ depends on the class $\mathcal{F}$ and if you don't have an explicit list of excluded minors, there might be no constructive way to find them. You cannot just take a bipartite graph and apply the theorem. The graph must be from some class $\mathcal{F}$ with the above properties.


---

