# A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs

arXiv: https://arxiv.org/abs/2101.10742 · HTML: https://mlsanity.com/paper/2101.10742/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jan 2021.

## Built on by (most cited first, 1 of 1)

- [Binary Quantized Neural Network Training Is W[1]-Hard Parameterized by Input and Output Dimensions](https://mlsanity.com/paper/2609.27932/) (2026)

## Abstract (arXiv)

(see paper for full abstract) We show that the Edge-Disjoint Paths problem is W[1]-hard parameterized by the number k of terminal pairs, even when the input graph is a planar directed acyclic graph (DAG). This answers a question of Slivkins (ESA '03, SIDMA '10). Moreover, under the Exponential Time Hypothesis (ETH), we show that there is no f(k)· no(k) algorithm for Edge-Disjoint Paths on planar DAGs, where k is the number of terminal pairs, n is the number of vertices and f is any computable function. Our hardness holds even if both the maximum in-degree and maximum out-degree of the graph are at most 2. Our result shows that the nO(k) algorithm of Fortune et al. (TCS '80) for Edge-Disjoint Paths on DAGs is asymptotically tight, even if we add an extra restriction of planarity. As a special case of our result, we obtain that Edge-Disjoint Paths on planar directed graphs is W[1]-hard parameterized by the number k of terminal pairs. This answers a question of Cygan et al. (FOCS '13) and Schrijver (pp. 417-444, Building Bridges II, '19), and completes the landscape of the parameterized complexity status of edge and vertex versions of the Disjoint Paths problem on planar directed and planar undirected graphs.