The well-known Disjoint Paths problem is to decide if a graph contains k pairwise disjoint paths, each connecting a different terminal pair from a set of k distinct pairs. We determine, with an exception of two cases, the complexity of the Disjoint Paths problem for H-free graphs. If k is fixed, we obtain the k-Disjoint Paths problem, which is known to be polynomial-time solvable on the class of all graphs for every k ≥ 1. However, the latter does no longer hold if we need to connect vertices from terminal sets instead of terminal pairs. We completely classify the complexity of k-Disconnected Connected Subgraphs for H-free graphs, and give the same almost-complete classification for Disjoint Connected Subgraphs for H-free graphs as for Disjoint Paths.

https://link.springer.com/chapter/10.1007/978-3-030-79987-8_29