Disjoint Paths Problem with Group-Expressable Constraints

We study an extension of the k-Disjoint Paths Problem where, in addition to finding k disjoint paths joining k given pairs of vertices in a graph, we ask that those paths satisfy certain constraints expressable by abelian groups. We give an O(n8) time algorithm to solve this problem under the assumption that the constraint can be expressed as avoiding a bounded number of group elements; moreover, our O(n8) algorithm allows any bounded number of such constraints to be combined. Examples of group-expressable constraints include: (1) paths of length ℓ modulo m for any fixed integers ℓ and m with m ≥ 2, (2) paths passing through a bounded number of prescribed sets of edges and/or vertices, and (3) paths that are long detours (si-ti-paths with length at least (si,ti)+ℓ for any fixed integer ℓ). The k=1 case of the problem with modularity constraints solves a problem in [Arkin, Papadimitriou, and Yannakakis, J. ACM, (1991)] that has remained open for over 30 years. Our work also implies a polynomial time algorithm for testing the existence of a subgraph isomorphic to a subdivision of a fixed graph, where each path of the subdivision between branch vertices satisfies any combination of a bounded number of group-expressable constraints. This in particular gives a unified polynomial time algorithm for testing the existence of k disjoint cycles with such constraints. For example, we can test in polynomial time the existence of k disjoint cycles in surface-embedded graphs such that each cycle is non-homologous to 0 and is at least ℓ longer than the minimum length of such a cycle. In addition, our work implies similar results addressing edge-disjointness.