Skip to main content

Research Repository

Advanced Search

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

Martin, Barnaby; Paulusma, Daniël; Smith, Siani; van Leeuwen, Erik Jan

Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs Thumbnail


Authors

Erik Jan van Leeuwen



Abstract

Paths P1,…,Pk in a graph G=(V,E) are mutually induced if any two distinct Pi and Pj have neither common vertices nor adjacent vertices. The INDUCED DISJOINT PATHS problem is to decide if a graph G with k pairs of specified vertices (si,ti) contains k mutually induced paths Pi such that each Pi starts from si and ends at ti . This is a classical graph problem that is NP-complete even for k=2 . We introduce a natural generalization, INDUCED DISJOINT CONNECTED SUBGRAPHS: instead of connecting pairs of terminals, we must connect sets of terminals. We give almost-complete dichotomies of the computational complexity of both problems for H-free graphs, that is, graphs that do not contain some fixed graph H as an induced subgraph. Finally, we give a complete classification of the complexity of the second problem if the number k of terminal sets is fixed, that is, not part of the input.

Citation

Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. J. (2023). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. Algorithmica, 85, 2580–2604. https://doi.org/10.1007/s00453-023-01109-z

Journal Article Type Article
Acceptance Date Feb 20, 2023
Online Publication Date Mar 11, 2023
Publication Date 2023
Deposit Date Apr 18, 2023
Publicly Available Date Apr 18, 2023
Journal Algorithmica
Print ISSN 0178-4617
Electronic ISSN 1432-0541
Publisher Springer
Peer Reviewed Peer Reviewed
Volume 85
Pages 2580–2604
DOI https://doi.org/10.1007/s00453-023-01109-z
Public URL https://durham-repository.worktribe.com/output/1175480

Files

Published Journal Article (Advanced online version) (535 Kb)
PDF

Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/

Copyright Statement
Advanced online version Open Access. This article is distributed under the terms of the Creative Commons Attribution License (CC-BY 4.0), which permits any use, distribution and reproduction in any medium, provided the original author(s) and source are credited.






You might also like



Downloadable Citations