P.A. Golovach
Induced disjoint paths in claw-free graphs
Golovach, P.A.; Paulusma, D.; van Leeuwen, E.J.
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 specied vertices (si; ti) contains k mutually induced paths Pi such that Pi connects si and ti for i = 1; : : : ; k. We show that this problem is xed-parameter tractable for claw-free graphs when parameterized by k. Several related problems, such as the k-in-a-Path problem, are proven to be xed-parameter tractable for claw-free graphs as well. We show that an improvement of these results in certain directions is unlikely, for example by noting that the Induced Disjoint Paths problem cannot have a polynomial kernel for line graphs (a type of clawfree graphs), unless NP coNP=poly. Moreover, the problem becomes NP-complete, even when k = 2, for the more general class of K1;4-free graphs. Finally, we show that the nO(k)-time algorithm of Fiala et al. for testing whether a claw-free graph contains some k-vertex graph H as a topological induced minor is essentially optimal by proving that this problem is W[1]-hard even if G and H are line graphs.
Citation
Golovach, P., Paulusma, D., & van Leeuwen, E. (2015). Induced disjoint paths in claw-free graphs. SIAM Journal on Discrete Mathematics, 29(1), 348-375. https://doi.org/10.1137/140963200
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 2015 |
Deposit Date | Dec 20, 2014 |
Publicly Available Date | Feb 13, 2015 |
Journal | SIAM Journal on Discrete Mathematics |
Print ISSN | 0895-4801 |
Electronic ISSN | 1095-7146 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 29 |
Issue | 1 |
Pages | 348-375 |
DOI | https://doi.org/10.1137/140963200 |
Keywords | Induced disjoint paths, Claw-free graphs, Parameterized complexity |
Public URL | https://durham-repository.worktribe.com/output/1447883 |
Files
Published Journal Article
(459 Kb)
PDF
Copyright Statement
© 2015 Society for Industrial and Applied Mathematics
You might also like
Computing balanced solutions for large international kidney exchange schemes
(2024)
Journal Article
An Algorithmic Framework for Locally Constrained Homomorphisms
(2024)
Journal Article
Solving problems on generalized convex graphs via mim-width
(2023)
Journal Article
The Complexity of Matching Games: A Survey
(2023)
Journal Article
Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs
(2023)
Journal Article
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 © 2025
Advanced Search