Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes

Binglin Tao, Mingyu Xiao, Jingyang ZhaoAAAI 2020 · DOI

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 reduction from a bipartite graph $B$ to a graph $G$ used to prove the NP-hardness of the general LDP problem.

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:

  1. 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$.
  2. 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.
Illustration of augmenting paths $P_1, P_2$, the residual graph $G'$, and their symmetric difference $P_1 \oplus P_2$ used in the LDP algorithm.

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.31 network (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

BibTeX
@inproceedings{tao2020finding,
  author = {Binglin Tao and Mingyu Xiao and Jingyang Zhao},
  title = {{Finding Minimum-Weight Link-Disjoint Paths with a Few Common Nodes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i01.5441},
}
Figure