Skip to main content

Research Repository

Advanced Search

Disjoint paths and connected subgraphs for H-free graphs

Kern, W.; Martin, B.; Paulusma, D.; Smith, S.; van Leeuwen, E.J.

Disjoint paths and connected subgraphs for H-free graphs Thumbnail


Authors

W. Kern

E.J. van Leeuwen



Contributors

Paola Flocchini
Editor

Lucia Moura
Editor

Abstract

The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k ≥ 1. The latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k-Disjoint Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths.

Citation

Kern, W., Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2021). Disjoint paths and connected subgraphs for H-free graphs. In P. Flocchini, & L. Moura (Eds.), Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings (414-427). https://doi.org/10.1007/978-3-030-79987-8_29

Acceptance Date May 1, 2021
Online Publication Date Jun 30, 2021
Publication Date 2021
Deposit Date May 28, 2021
Publicly Available Date Jun 1, 2021
Publisher Springer Verlag
Volume 12757
Pages 414-427
Series Title Lecture Notes in Computer Science
Series ISSN 0302-9743
Book Title Combinatorial Algorithms: 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5–7, 2021, Proceedings
ISBN 9783030799861
DOI https://doi.org/10.1007/978-3-030-79987-8_29
Public URL https://durham-repository.worktribe.com/output/1625144

Files





You might also like



Downloadable Citations