English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Given a graph G and a set T = { (si, ti) : 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 P1,P2, . . . ,Pk 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 nO(k) time algorithm which was later improved upon by Cygan et al. (FOCS ’13) who designed an FPT algorithm running in 22 O(k2) · nO(1) time. To the best of our knowledge, the parameterized complexity of EDGE-DISJOINT PATHS on planar1 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) ·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. We now place our result in the context of previously known algorithms and hardness for EDGEDISJOINT PATHS on special classes of directed graphs: • Implications for EDGE-DISJOINT PATHS on DAGs: 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. The previous best lower bound (also under ETH) for EDGE-DISJOINT PATHS on DAGs was f (k) ·no(k/ logk) by Amiri et al. (MFCS ’16, IPL ’19) which improved upon the f (k) · no( √ 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 (see Table 2) of the parameterized complexity status of edge and vertex versions of the DISJOINT PATHS problem on planar directed and planar undirected graphs.

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