On graph contractions and induced minors

The Induced Minor Containment problem takes as input two graphs GG and HH, and asks whether GG has HH as an induced minor. We show that this problem is fixed parameter tractable in |VH||VH| if GG belongs to any nontrivial minor-closed graph class and HH is a planar graph. For a fixed graph HH, the HH-Contractibility problem is to decide whether a graph can be contracted to HH. The computational complexity classification of this problem is still open. So far, HH has a dominating vertex in all cases known to be solvable in polynomial time, whereas HH does not have such a vertex in all cases known to be NP-complete. Here, we present a class of graphs HH with a dominating vertex for which HH-Contractibility is NP-complete. We also present a new class of graphs HH for which HH-Contractibility can be solved in polynomial time. Finally, we study the (H,v)(H,v)-Contractibility problem, where vv is a vertex of HH. The input of this problem is a graph GG and an integer kk, and the question is whether GG is HH-contractible such that the “bag” of GG corresponding to vv contains at least kk vertices. We show that this problem is NP-complete whenever HH is connected and vv is not a dominating vertex of HH.