Detecting induced minors in AT-free graphs

Golovach, P.A.; Kratsch, D.; Paulusma, D.

Abstract

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 |VH|.

Citation

Golovach, P., Kratsch, D., & Paulusma, D. (2013). Detecting induced minors in AT-free graphs. Theoretical Computer Science, 482, 20-32. https://doi.org/10.1016/j.tcs.2013.02.029

• Journal Article Type: Article
• Publication Date: Apr 22, 2013
• Deposit Date: Mar 11, 2013
• Publicly Available Date: Apr 19, 2013
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 482
• Pages: 20-32
• DOI: https://doi.org/10.1016/j.tcs.2013.02.029
• Keywords: Induced minor, Contraction, AT-free graphs.
• Public URL: https://durham-repository.worktribe.com/output/1495879