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

Given a graph G and a set T = {(s_i,t_i) : 1 ≤ i ≤ k} of k pairs, the VERTEX-DISJOINT PATHS (resp. EDGE-DISJOINT PATHS) problems asks to determine whether there exist pairwise vertex-disjoint (resp. edge-disjoint) paths P₁, P₂, . . . , P_k in G such that Pi connects si to ti for each 1 ≤ i ≤ k. Unlike their undirected counterparts which are FPT (parameterized by k) from Graph Minor theory, both the edge-disjoint and vertex-disjoint versions in directed graphs were shown by Fortune et al. (TCS ’80) to be NP-hard for k = 2. This strong hardness for DISJOINT PATHS on general directed graphs led to the study of parameterized complexity on special graph classes, e.g., when the underlying undirected
graph is planar. For VERTEX-DISJOINT PATHS on planar directed graphs, Schrijver (SICOMP ’94) designed an n^O(k) time algorithm which was later improved upon by Cygan et al. (FOCS ’13) who designed an FPT algorithm running in 2^2O(k2)· n^O(1) time. To the best of our knowledge, the parameterized complexity of EDGE-DISJOINT PATHS on planar directed graphs is unknown.

We resolve this gap by showing that EDGE-DISJOINT PATHS 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) · n^o(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.

We now place our result in the context of previously known algorithms and hardness for EDGE-DISJOINT PATHS on special classes of directed graphs:

• Implications for EDGE-DISJOINT PATHS on DAGs: Our result shows that the n^O(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. The previous best lower bound (also under ETH) for EDGE-DISJOINT PATHS on DAGs was f (k) · n^{o(k/ log k)} by Amiri et al. (MFCS ’16, IPL ’19) which improved upon the f (k) · n^o(√k) lower bound implicit in Slivkins (ESA ’03, SIDMA ’10).

• Implications for EDGE-DISJOINT PATHS on planar directed graphs: 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.