Edge-Disjoint Paths in Eulerian Digraphs

View PDF

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 (Graph Minors XIII) 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 (Marx 2004) 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. Ibaraki, Poljak 1991; Frank 1988; Frank, Ibaraki, Nagamochi 1995).
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 (1995) 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 Chapter 4 of Bang-Jensen, Gutin 2018 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.