The directed 2-linkage problem with length constraints
Pith reviewed 2026-05-25 11:28 UTC · model grok-4.3
The pith
For any fixed constants k1 and k2 there is a polynomial algorithm deciding existence of arc-disjoint paths each at most ki longer than shortest in a digraph.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The paper proves that for every pair of constants k1, k2, there is a polynomial algorithm which decides whether the input digraph D has a pair of arc-disjoint paths P1, P2 such that Pi is an (si,ti)-path and the length of Pi is no more than d(si,ti)+ki, for i=1,2, where d(si,ti) denotes the length of the shortest (si,ti)-path.
What carries the argument
The pair of fixed additive length bounds k1 and k2 that cap the excess length of each path over its shortest possible distance.
If this is right
- The decision problem lies in P whenever the excesses are bounded by any fixed constants.
- No polynomial algorithm exists for the version with excess c log to the 1+ε of n unless the exponential time hypothesis fails.
- The weak 2-linkage problem is NP-complete when one path is forced to be a shortest path and the other path has unbounded length.
- The result separates the constant-excess regime from both the unrestricted case and the logarithmic-excess case.
Where Pith is reading between the lines
- Tractability appears to hinge on the excesses remaining constant rather than growing with input size.
- The same bounded-excess technique may apply to other path-linkage problems that tolerate small detours.
- Practical network-routing tasks that accept minor length increases could become efficiently solvable.
Load-bearing premise
The allowed excesses k1 and k2 are fixed constants independent of the number of vertices in the input digraph.
What would settle it
An explicit reduction from an NP-hard problem to the weak 2-linkage decision problem for some specific fixed constants k1 and k2.
Figures
read the original abstract
The {\sc weak 2-linkage} problem for digraphs asks for a given digraph and vertices $s_1,s_2,t_1,t_2$ whether $D$ contains a pair of arc-disjoint paths $P_1,P_2$ such that $P_i$ is an $(s_i,t_i)$-path. This problem is NP-complete for general digraphs but polynomially solvable for acyclic digraphs \cite{fortuneTCS10}. Recently it was shown \cite{bercziESA17} that if $D$ is equipped with a weight function $w$ on the arcs which satisfies that all edges have positive weight, then there is a polynomial algorithm for the variant of the weak-2-linkage problem when both paths have to be shortest paths in $D$. In this paper we consider the unit weight case and prove that for every pair constants $k_1,k_2$, there is a polynomial algorithm which decides whether the input digraph $D$ has a pair of arc-disjoint paths $P_1,P_2$ such that $P_i$ is an $(s_i,t_i)$-path and the length of $P_i$ is no more than $d(s_i,t_i)+k_i$, for $i=1,2$, where $d(s_i,t_i)$ denotes the length of the shortest $(s_i,t_i)$-path. We prove that, unless the exponential time hypothesis (ETH) fails, there is no polynomial algorithm for deciding the existence of a solution $P_1,P_2$ to the {\sc weak 2-linkage} problem where each path $P_i$ has length at most $d(s_i,t_i)+ c\log^{1+\epsilon}{}n$ for some constant $c$. We also prove that the {\sc weak 2-linkage} problem remains NP-complete if we require one of the two paths to be a shortest path while the other path has no restriction on the length.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the weak 2-linkage problem on digraphs with unit arc weights. It claims a polynomial-time algorithm, for any fixed constants k1 and k2, that decides existence of arc-disjoint (si,ti)-paths Pi whose length is at most d(si,ti)+ki. It further claims an ETH-based lower bound ruling out polynomial algorithms when the allowed excess is c log^{1+ε}n, and NP-completeness when one path is required to be shortest while the other has no length bound.
Significance. The positive result extends the known polynomial-time solvability on acyclic digraphs and for exact shortest paths to the setting of bounded additive excess on general digraphs. The ETH and NP-completeness results delineate the boundary between tractable and intractable variants. The fixed-k regime yields a clean algorithmic contribution without hidden parameters.
minor comments (2)
- [Abstract] The abstract states the main algorithmic result for unit weights but does not repeat the unit-weight hypothesis in the sentence describing the k1,k2 algorithm; a single clarifying clause would improve readability.
- The citation to bercziESA17 is given without a full bibliographic entry in the provided abstract; ensure the reference list is complete in the full manuscript.
Simulated Author's Rebuttal
We thank the referee for the positive review, the accurate summary of our results, and the recommendation to accept. No major comments were raised in the report.
Circularity Check
No significant circularity identified
full rationale
The paper's central positive result is a polynomial-time algorithm for the weak 2-linkage problem with fixed additive length bounds k1,k2 on unit-weight digraphs. This is established via explicit algorithmic constructions and reductions that operate directly on the input digraph, extending known polynomial solvability for acyclic digraphs and shortest-path variants without reducing the new claim to a fit, self-definition, or load-bearing self-citation. The separate ETH-based logarithmic lower bound and NP-completeness result for the mixed shortest/unrestricted case are independent statements proved by reduction and do not feed back into the polynomial algorithm. No equations or steps in the derivation chain equate a claimed prediction or uniqueness result to its own inputs by construction.
Axiom & Free-Parameter Ledger
axioms (2)
- domain assumption The exponential time hypothesis (ETH) holds
- standard math Standard definitions of directed graphs, paths, and arc-disjointness
Reference graph
Works this paper leans on
-
[1]
J. Bang-Jensen and Gutin. G (eds.). Classes of Directed Graphs . Springer Mono- graphs in Mathematics. Springer Verlag, London, 2018
work page 2018
-
[2]
J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications . Springer-Verlag, London, 2nd edition, 2009
work page 2009
-
[3]
A. Bj¨ orklund and T. Husfeldt. Shortest two disjoint paths in po lynomial time. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 9 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, P art I , pages 211–222, 2014
work page 2014
-
[4]
M. Cygan, F.V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipc zuk, M. Pilipczuk, and S. Saurabh. Parameterized Algorithms. Springer, 2015
work page 2015
-
[5]
´E. Colin de Verdi` ere and A. Schrijver. Shortest vertex-disjoint two-face paths in planar graphs. ACM Trans. Algorithms , 7(2):19:1–19:12, 2011
work page 2011
-
[6]
T. Eilam-Tzoreff. The disjoint shortest paths problem. Discrete Applied Mathemat- ics, 85(2):113–138, 1998
work page 1998
-
[7]
S. Fortune, J.E. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theor. Comput. Sci. , 10:111–121, 1980
work page 1980
-
[8]
K. Kawarabayashi, Y. Kobayashi, and B. A. Reed. The disjoint pa ths problem in quadratic time. J. Comb. Theory, Ser. B , 102(2):424–435, 2012
work page 2012
- [9]
-
[10]
Y. Kobayashi and C. Sommer. On shortest disjoint paths in plan ar graphs. Discrete Optimization, 7(4):234–245, 2010
work page 2010
-
[11]
N. Robertson and P.D. Seymour. Graph minors. XIII: The disjo int paths problem. J. Combin. Theory Ser. B , 63:65–110, 1995
work page 1995
- [12]
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.