On graph contractions and induced minors

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