Few induced disjoint paths for H-free graphs

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

Abstract

Paths in a graph are mutually induced if any two distinct and have neither common vertices nor adjacent vertices. For a fixed integer k, the k-Induced Disjoint Paths problem is to decide if a graph G with k pairs of specified vertices contains k mutually induced paths such that each starts from and ends at . Whereas the non-induced version is well-known to be polynomial-time solvable for every fixed integer k, a classical result from the literature states that even 2-Induced Disjoint Paths is NP-complete. We prove new complexity results for k-Induced Disjoint Paths if the input is restricted to H-free graphs, that is, graphs without a fixed graph H as an induced subgraph. We compare our results with a complexity dichotomy for Induced Disjoint Paths, the variant where k is part of the input.

Citation

Martin, B., Paulusma, D., Smith, S., & van Leeuwen, E. (2023). Few induced disjoint paths for H-free graphs. Theoretical Computer Science, 939, 182-193. https://doi.org/10.1016/j.tcs.2022.10.024

• Journal Article Type: Article
• Acceptance Date: Oct 19, 2022
• Online Publication Date: Nov 14, 2022
• Publication Date: Jan 4, 2023
• Deposit Date: Oct 29, 2022
• Publicly Available Date: Oct 31, 2022
• Journal: Theoretical Computer Science
• Print ISSN: 0304-3975
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 939
• Pages: 182-193
• DOI: https://doi.org/10.1016/j.tcs.2022.10.024
• Public URL: https://durham-repository.worktribe.com/output/1187799