Detecting induced minors in AT-free graphs

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

Abstract

The problem Induced Minor is to test whether a graph G can be modified into a graph H by a sequence of vertex deletions and edge contractions. 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. Our result can be considered to be optimal in some sense as we also prove that Induced Minor is W[1]-hard on AT-free graphs, when parameterized by |VH|. In order to obtain it we prove that the Set-Restricted k-Disjoint Paths problem can be solved in polynomial time on AT-free graphs for any fixed k. We also use the latter result to prove that the Set-Restricted k-Disjoint Connected Subgraphs problem is polynomial-time solvable on AT-free graphs for any fixed k.

Citation

Golovach, P. A., Kratsch, D., & Paulusma, D. (2012, December). Detecting induced minors in AT-free graphs

• Presentation Conference Type: Conference Paper (published)
• Publication Date: 2012
• Deposit Date: Mar 11, 2013
• Print ISSN: 0302-9743
• Volume: 7676
• Pages: 495-505
• Series Title: Lecture notes in computer science
• Series Number: 7676
• Series ISSN: 0302-9743,1611-3349
• Book Title: Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings.
• ISBN: 9783642352607
• DOI: https://doi.org/10.1007/978-3-642-35261-4_52
• Public URL: https://durham-repository.worktribe.com/output/1157406
• Additional Information: Series: Lecture Notes in Computer Science, Volume 7676