Few induced disjoint paths for H-free graphs

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

Abstract

Paths P 1 , . . . , P k in a graph G = (V, E) are mutually induced if any two distinct P i and P j 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 (si, ti) contains k mutually induced paths P i such that each P i starts from si and ends at ti. 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. (2022). Few induced disjoint paths for H-free graphs. In I. Ljubić, F. Barahona, S. S. Dey, & A. Ridha Mahjoub (Eds.), Combinatorial Optimization 7th International Symposium, ISCO 2022 (89-101). https://doi.org/10.1007/978-3-031-18530-4_7

• Conference Name: ISCO 2022
• Conference Location: Online
• Start Date: May 18, 2022
• End Date: May 20, 2022
• Acceptance Date: Jun 13, 2022
• Online Publication Date: Nov 21, 2022
• Publication Date: 2022
• Deposit Date: Oct 16, 2022
• Publicly Available Date: Nov 22, 2023
• Publisher: Springer
• Volume: 13526
• Pages: 89-101
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Combinatorial Optimization 7th International Symposium, ISCO 2022
• DOI: https://doi.org/10.1007/978-3-031-18530-4_7
• Public URL: https://durham-repository.worktribe.com/output/1135339
• Publisher URL: https://isco2022.sciencesconf.org/