P. A Golovach
Detecting induced minors in AT-free graphs
Golovach, P. A; Kratsch, D.; Paulusma, D.
Authors
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
Matching cuts in graphs of high girth and H-free graphs
(2023)
Conference Proceeding
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
On the price of independence for vertex cover, feedback vertex set and odd cycle transversal
(2023)
Journal Article
Computing Subset Vertex Covers in H-Free Graphs
(2023)
Conference Proceeding
Dichotomies for Maximum Matching Cut: H-Freeness, Bounded Diameter, Bounded Radius
(2023)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search