P. A. Golovach
Induced disjoint paths in AT-free graphs
Golovach, P. A.; Paulusma, D.; van Leeuwen, E. J.
Authors
Contributors
Fedor V. Fomin
Editor
Petteri Kaski
Editor
Abstract
Paths P1,…,Pk in a graph G = (V,E) are said to be mutually induced if for any 1 ≤ i < j ≤ k, Pi and Pj have neither common vertices nor adjacent vertices (except perhaps their end-vertices). The Induced Disjoint Paths problem is to test whether a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that Pi connects si and ti for i = 1,…,k. This problem is known to be NP-complete already for k = 2. We prove that it can be solved in polynomial time for AT-free graphs even when k is part of the input. As a consequence, the problem of testing whether a given AT-free graph contains some graph H as an induced topological minor admits a polynomial-time algorithm, as long as H is fixed; we show that such an algorithm is essentially optimal by proving that the problem is W[1]-hard, even on a subclass of AT-free graphs, namely cobipartite graphs, when parameterized by |VH|. We also show that the problems k-in-a-Path and k-in-a-Tree can be solved in polynomial time, even when k is part of the input. These problems are to test whether a graph contains an induced path or induced tree, respectively, spanning k given vertices.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Publication Date | 2012 |
Deposit Date | Mar 11, 2013 |
Pages | 153-164 |
Series Title | Lecture notes in computer science |
Series Number | 7357 |
Series ISSN | 0302-9743,1611-3349 |
Book Title | Algorithm Theory : 13th Scandinavian Symposium and Workshops, SWAT 2012, Helsinki, Finland, 4-6 July 2012 ; proceedings. |
ISBN | 9783642311543 |
DOI | https://doi.org/10.1007/978-3-642-31155-0_14 |
Public URL | https://durham-repository.worktribe.com/output/1156971 |
Additional Information | Series: Lecture Notes in Computer Science, Volume 7357 |
You might also like
Classifying Subset Feedback Vertex Set for H-free graphs
(2022)
Presentation / Conference Contribution
Few induced disjoint paths for H-free graphs
(2022)
Presentation / Conference Contribution
An algorithmic framework for locally constrained homomorphisms
(2022)
Presentation / Conference Contribution
The Complexity of L(p,q)-Edge-Labelling
(2022)
Presentation / Conference Contribution
Computing Balanced Solutions for Large International Kidney Exchange Schemes
(2022)
Presentation / Conference Contribution
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