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.
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.
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