Skip to main content

Research Repository

Advanced Search

Detecting induced minors in AT-free graphs

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

Authors

P. A Golovach

D. Kratsch



Contributors

Kun-Mao Chao
Editor

Tsan-sheng Hsu
Editor

Der-Tsai Lee
Editor

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). Detecting induced minors in AT-free graphs. In K. Chao, T. Hsu, & D. Lee (Eds.), Algorithms and computation : 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, 19-21 December 2012 ; proceedings (495-505). https://doi.org/10.1007/978-3-642-35261-4_52

Publication Date 2012
Deposit Date Mar 11, 2013
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


You might also like



Downloadable Citations