@inproceedings{fea22e9e5ae64571a5258137ef286bbc,
title = "Few Induced Disjoint Paths for H-Free Graphs",
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. 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 Pi such that each Pi 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.",
keywords = "Induced disjoint paths, H-free graph, Complexity, dichotomy",
author = "Barnaby Martin and Dani{\"e}l Paulusma and Siani Smith and {van Leeuwen}, {Erik Jan}",
year = "2022",
doi = "10.1007/978-3-031-18530-4_7",
language = "English",
isbn = "978-3-031-18529-8",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "89--101",
editor = "Ljubi{\'c}, {Ivana } and Barahona, {Francisco } and Dey, {Santanu S. } and Mahjoub, {A. Ridha}",
booktitle = "Combinatorial Optimization - 7th International Symposium, ISCO 2022, Virtual Event, May 18-20, 2022, Revised Selected Papers",
}