Edge-Disjoint Paths in Eulerian Digraphs

Disjoint paths problems are among the most prominent problems in combinatorial optimisation. The edge- as well as the Vertex-Disjoint Paths problem are NP-complete, both on directed and undirected graphs. But on undirected graphs, Robertson and Seymour developed an algorithm for both problems that runs in cubic time for every fixed number ‍p of terminal pairs, i.e. they proved that the problem is fixed-parameter tractable on undirected graphs. This is in sharp contrast to the situation on directed graphs, where Fortune, Hopcroft, and Wyllie proved that both problems are NP-complete already for ‍p=2 terminal pairs. In this paper, we study the Edge-Disjoint Paths problem (EDPP) on Eulerian digraphs, a problem that has received significant attention in the literature. Marx proved that the Eulerian EDPP is NP-complete even on structurally very simple Eulerian digraphs. On the positive side, polynomial time algorithms are known only for very restricted cases, such as ‍p≤ 3 or where the demand graph is a union of two stars. The question for which values of ‍p the Edge-Disjoint Paths problem can be solved in polynomial time on Eulerian digraphs has already been raised by Frank, Ibaraki, and Nagamochi almost 30 years ago. But despite considerable effort, the complexity of the problem is still wide open and is considered to be the main open problem in this area. In this paper, we solve this long-open problem by showing that the Edge-Disjoint Paths problem is fixed-parameter tractable on Eulerian digraphs in general (parameterized by the number of terminal pairs). The algorithm itself is reasonably simple but the proof of its correctness requires a deep structural analysis of Eulerian digraphs.