Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

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

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