Skip to main content

Research Repository

Advanced Search

Detecting induced minors in AT-free graphs

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

Detecting induced minors in AT-free graphs Thumbnail


Authors

P.A. Golovach

D. Kratsch



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 Mar 29, 2024
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

Files

Accepted Journal Article (396 Kb)
PDF

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Theoretical computer science. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Theoretical computer science, 482, 22 April 2013, 10.1016/j.tcs.2013.02.029





You might also like



Downloadable Citations