The INDUCED MINOR problem is that of testing whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. If only edge contractions are permitted, we obtain the CONTRACTIBILITY problem. We prove that INDUCED MINOR is polynomial-time solvable when G is AT-free and H is fixed, i.e., not part of the input. In addition, we show that CONTRACTIBILITY is polynomial-time solvable when G is AT-free and H is a fixed triangle-free graph. We complement these two results by proving that both problems are W[1]-hard on AT-free graphs when parameterized by |V_H|.
展开▼
