# H-induced Containment problem

In the paper "On Graph Contractions and Induced Minors" by Pim van't Hof et al. they showed that this problem is fi xed 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.

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.