Introduction
In modern network engineering, ensuring "survivability"—the ability of a network to maintain connectivity despite link failures—is a critical requirement. Traditionally, this is achieved by finding node-disjoint or link-disjoint paths between a source and a destination. However, in many real-world scenarios, such as those with geographical constraints or limited resources (e.g., power, spectrum, or memory), achieving total disjointness is either impossible or prohibitively expensive.
This research explores a practical middle ground: "partially disjoint paths." These paths are strictly link-disjoint but are allowed to share a limited number of "common nodes" ($\delta$). While the problem of finding two such paths ($k=2$) is well-understood, the complexity and algorithmic solutions for $k \ge 3$ paths remained an open challenge until this study.
Complexity and NP-Hardness
The authors first address the theoretical complexity of the general $(k, \delta)$-Link-Disjoint Path (LDP) problem. They prove that finding $k$ minimum-weight link-disjoint paths with at most $\delta$ common nodes is NP-hard for any $k \ge 3$.
The proof involves a reduction from the "densest $\delta$ subgraph problem" in bipartite graphs, as illustrated in the figure above. This finding is significant because it explains why simple polynomial-time solutions for the general case have been elusive and shifts the focus toward finding efficient algorithms for restricted versions of the problem.
The LDP Algorithm
To provide a practical solution, the authors introduce a polynomial-time algorithm for a "restricted" version of the problem. In this version, while the total number of common nodes is capped at $\delta$, each node can be shared by at most two paths. This constraint aligns with real-world hardware limitations, such as "Splitter-and-Delivery" (SAD) switches used in multicasting.
The proposed LDP algorithm leverages two core concepts from graph theory:
- Node Splitting: Nodes are split into two with a connecting link that has a specific cost. "Buying" this link counts toward the common node budget $\delta$.
- Augmenting Paths in Residual Graphs: The algorithm iteratively finds paths in a specialized "Restricted Residual Graph." This structure allows the algorithm to "undo" previous path selections if a more optimal global set of paths is found.
As shown in the figure, the residual graph approach ensures that the algorithm can explore various path combinations while strictly adhering to the common node budget. The resulting algorithm has a time complexity of $O((\delta + 1)k|E||V|)$.
Experimental Results
The authors evaluated the LDP algorithm against a standard Integer Linear Programming (ILP) baseline using both synthetic and real-world datasets from the Stanford Large Network Dataset Collection (SNAP).
- Efficiency: The LDP algorithm significantly outperformed the ILP solver. On the
p2p-Gnut.31network (approx. 62,000 nodes), the LDP algorithm found solutions in 10–13 seconds, whereas the ILP solver required over a minute. - Scalability: The algorithm demonstrated excellent scalability, handling massive graphs with up to 100,000 links with ease. This makes it a viable candidate for optimizing large-scale ISP backbone networks.
Conclusion
This research provides a crucial theoretical and practical framework for network survivability. By identifying the NP-hardness of the general problem and offering a fast, $O((\delta + 1)k|E||V|)$ algorithm for the restricted case, the authors bridge the gap between theory and practice. Future work may involve investigating the exact complexity for specific values of $k$ and exploring approximation algorithms for the general NP-hard version where nodes can be shared by more than two paths.
Summary updated