An exact characterization of tractable demand patterns for maximum disjoint path problems

We study the following general disjoint paths problem: given a supply graph G, a set T ⊆ V(G) of terminals, a demand graph H on the vertices T, and an integer k, the task is to find a set of k pairwise vertex-disjoint valid paths, where we say that a path of the supply graph G is valid if its endpoints are in T and adjacent in the demand graph H. For a class H of graphs, we denote by Maximum Disjoint ℋ-Paths the restriction of this problem when the demand graph H is assumed to be a member of ℋ. We study the fixed-parameter tractability of this family of problems, parameterized by k. Our main result is a complete characterization of the fixed-parameter tractable cases of Maximum Disjoint ℋ-Paths for every hereditary class ℋ of graphs: it turns out that complexity depends on the existence of large induced matchings and large induced skew bicliques in the demand graph H (a skew biclique is a bipartite graph on vertices a1, …, an, b1, …, bn with ai and bj being adjacent if and only if i ≤ j). Specifically, we prove the following classification for every hereditary class ℋ. If ℋ does not contain every matching and does not contain every skew biclique, then MAXIMUM Disjoint ℋ-Paths is FPT. If ℋ does not contain every matching, but contains every skew biclique, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard, admits an FPT approximation, and the valid paths satisfy an analog of the Erdös-Pósa property. If ℋ contains every matching, then MAXIMUM DISJOINT ℋ-Paths is W[1]-hard and the valid paths do not satisfy the analog of the Erdös-Pósa property.