Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions

Keerti Choudhary, Amit Kumar, Lakshay SaggiITCS 2026 · DOI

Abstract

The 2-Disjoint Shortest Paths (2-DSP) problem in directed graphs has long been a significant challenge in combinatorial optimization. This paper presents a major algorithmic breakthrough, improving the best-known running time from $O(m^5n)$ to a near-optimal $O(mn \log n)$. By employing an algebraic framework based on path-enumerating polynomials over fields of characteristic two, the authors effectively handle the complexities of directed cycles. Additionally, the paper introduces the Minimum 2-Disjoint Shortest Paths (Min-2-DSP) problem, providing the first efficient algorithms to minimize vertex intersections between shortest paths.

Introduction: The Challenge of Directed Graphs

Finding two vertex-disjoint shortest paths—one from $s_1$ to $t_1$ and another from $s_2$ to $t_2$—is a well-understood problem in undirected graphs and Directed Acyclic Graphs (DAGs). However, general directed graphs have remained difficult due to the lack of a global topological ordering. In a DAG, one can easily identify a "first" intersection point. In contrast, paths in general directed graphs can intersect, separate, and re-intersect in complex, non-linear patterns, as illustrated in Figure 1.

Visualizing path intersections in directed graphs: (a) a single intersection point $v$; (b) complex re-intersecting paths $P_1$ and $P_2$ that complicate traditional topological approaches.

Methodology: Algebraic Framework and Cancellation

The authors address these complexities using an algebraic approach. They associate each edge with a variable and represent a path as a monomial. The sum of all such monomials for all shortest paths forms an enumerating polynomial. By evaluating these polynomials over a field of characteristic two (where $1 + 1 = 0$), the authors exploit a "cancellation" property: "twin-crossing" paths—pairs that intersect and swap segments—cancel each other out. This leaves only the contribution of disjoint paths, allowing for efficient detection.

Structural Insights: The 'First Intersection' Logic

To handle directed cycles, the paper develops a novel recursive formula. A key insight is the definition of the "first intersection point" in a general digraph. A vertex $v$ is considered the first intersection on path $P_1$ if the prefixes of both paths and the suffix of the second path are all mutually disjoint. This structural requirement enables a dynamic programming approach to evaluate the polynomials efficiently.

Structural decomposition for identifying the 'first intersection' point $v$ and managing path interactions $P_1$ and $P_2$.

Key Results and Complexity Improvements

The proposed algorithms achieve significant performance gains:

  • 2-DSP in Directed Graphs: Running time improved to $O(mn \log n)$, down from $O(m^5n)$.
  • Min-2-DSP in Directed Graphs: The first efficient algorithm for this problem, with a complexity of $O(m^2n^3)$.
  • Optimal Bounds for DAGs/Undirected Graphs: Min-2-DSP solved in linear time, $O(m+n)$.
  • Path Reporting: The algorithms can explicitly output the paths in $O(mn^2 \log n)$ for 2-DSP and $O(m^2n^4)$ for Min-2-DSP.

Conclusion and Future Directions

While this work provides a near-optimal solution for $k=2$ disjoint shortest paths, several challenges remain. The current 2-DSP algorithm is restricted to graphs without negative or zero-weight cycles, as the latter makes the problem NP-hard. Furthermore, extending these algebraic methods to $k \geq 3$ paths remains an open problem, as the complexity landscape for higher values of $k$ is significantly more hostile. Future research may bridge the gap between detection and reporting times across different graph classes.

Summary updated

BibTeX
@inproceedings{choudhary2026efficient,
  author = {Keerti Choudhary and Amit Kumar and Lakshay Saggi},
  title = {{Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions}},
  booktitle = {ITCS},
  year = {2026},
  doi = {10.4230/lipics.itcs.2026.39},
}
Figure