Detecting induced minors in AT-free graphs

作者：Golovach Petr A^*; Kratsch Dieter; Paulusma Daniel

来源：Theoretical Computer Science, 2013, 482: 20-32.

DOI：10.1016/j.tcs.2013.02.029

• Induced minor
• Contraction
• AT-free graphs

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 vertical bar V-H vertical bar.

• 出版日期2013-4-22