4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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