Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs

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

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. (2022). Induced Disjoint Paths and Connected Subgraphs for H-Free Graphs. In Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers (398-411). https://doi.org/10.1007/978-3-031-15914-5_29

• Acceptance Date: Jul 15, 2022
• Online Publication Date: Oct 1, 2022
• Publication Date: 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Oct 2, 2023
• Publisher: Springer Verlag
• Volume: 13453
• Pages: 398-411
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Graph-Theoretic Concepts in Computer Science. 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers
• ISBN: 9783031159138
• DOI: https://doi.org/10.1007/978-3-031-15914-5_29
• Public URL: https://durham-repository.worktribe.com/output/1643993