Edge-Disjoint Paths in Eulerian Digraphs

Disjoint paths problems are among the most prominent problems in combinatorial optimization. The edge-as well as vertex-disjoint paths problem, are NP-complete on directed and undirected graphs. But on undirected graphs, Robertson and Seymour [RS95] developed an algorithm for the vertex-and the edge-disjoint paths problem 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.

On directed graphs, 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 [Mar04a] 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 (see e.g. [IP91, Fra88, FIN95]).

The question of 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 [FIN95] 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 (see [BG18, Chapter 4] for a recent survey).

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.