ShareDP : Finding k Disjoint Paths for Multiple Vertex Pairs

Zhiqiu Yuan, Youhuan Li, Lei Zou ✉, Linglin Yang · 2025

Read ShareDP : Finding k Disjoint Paths for Multiple Vertex Pairs by Zhiqiu Yuan, Youhuan Li, Lei Zou ✉, Linglin Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16506.txt.

Introduction

Zhiqiu Yuan and co-authors speed up batch searches for disjoint paths in networks, in a 2025 paper. Disjoint paths share no middle points, so they give backup routes. Transport and network routing issue many such queries at once. Handling each query alone wastes repeated work.

Simple extensions of path listing explode in cost. Single-query methods convert the graph but cannot share effort. Their algorithm, ShareDP, merges the converted graphs across queries. Computation and storage are then shared. That sharing cuts the batch cost while keeping the disjointness guarantee. The work serves planners who need many safe route options at once, such as in chip wiring or freight.

Catalog record

CREATORZhiqiu Yuan, Youhuan Li, Lei Zou ✉, Linglin Yang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16506

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ShareDP : Finding k Disjoint Paths for Multiple Vertex Pairs Zhiqiu Yuan, Youhuan Li, Lei Zou ✉, Linglin Yang Abstract Finding k k disjoint paths ( k k DP) is a fundamental problem in graph analysis. For vertices s s and t t , paths from s s to t t are said to be disjoint if any two of them share no common vertex except s s and t t . In practice, disjoint paths are widely applied in network routing and transportation. In these scenarios, multiple k k DP queries are often issued simultaneously, necessitating efficient batch processing. This motivates the study of batch k k DP query processing ( batch- k k DP ). A straightforward approach to batch- k k DP extends batch simple-path enumeration with disjointness checks. But this suffers from factorial computational complexity. An alternative approach leverages single-query algorithms that avoid this by replacing the graph with a converted version. However, handling each query independently misses opportunities for shared computation. To overcome these limitations, we propose ShareDP , an algorithm for batch- k k DP that share s the computation and storage across k k DP s. ShareDP merges converted graphs into a shared structure, then shares the traversals and operations from different queries within this structure. Extensive experiments on 12 real-world datasets confirm the superiority of ShareDP over comparative approaches. 1 Introduction Finding k disjoint paths ( k DP) is a fundamental challenge in graph analysis [ 4 , 13 , 5 , 8 , 2 , 11 ] . Given a source and a target vertex, k DP identifies k paths that do not share any vertices except for the source and target 1 1 1 We focus on vertex-disjoint paths, as edge-disjoint path finding problem can be reduced to vertex-disjoint version in polynomial time [ 12 ] . . Fig. 1(a) illustrates an example with disjoint paths p_{1} (red) and p_{2} (blue). Applications of k DP include cyber-security, network fault tolerance, and load balancing [ 6 , 9 , 8 , 2 , 11 ] . In practice, multiple k DP queries are often processed in batches. For example, as communication networks scale with the Internet, numerous routing queries are generated quickly, necessitating high-throughput processing. This paper focuses on the problem of batch k DP query processing ( batch- k DP ), where given a graph G and a set of k DP queries Q , returns k disjoint paths for each query in Q . Existing studies on k DP can be categorized into single-query [ 4 , 13 , 5 , 8 , 2 , 11 ] and single-source [ 6 , 3 , 1 ] . (1) Single-query methods include flow-augmenting path-based [ 4 , 13 , 5 ] and dissimilar path-based [ 8 , 2 , 11 ] . The latter extends simple path enumeration by incorporating disjointness constraints, but suffers from factorial time complexity (see Sec. 3.1 ). In contrast, the former achieves linear time complexity using split-graphs [ 4 , 5 , 13 ] , where finding disjoint paths reduces to identifying flow-augmenting paths in the split-graphs. (2) Single-source k DP seeks disjoint paths from a source to all other vertices, with current studies primarily theoretical and limited to k\leq 4 [ 1 ] . (3) To our knowledge, this paper is the first to address batch- k DP with general k . For batch- k DP , we can adapt methods from single-query k DP: (1) Dissimilar path-based methods can extend batch path enumeration algorithms [ 15 ] but also face factorial complexity. (2) Flow-augmenting path-based methods handle each query in linear time but require independent split-graphs for each query, missing opportunities for shared computation This leads to the question: can we apply existing batch-processing techniques from other problems? Unfortunately, current techniques are designed for queries in the same graph [ 15 , 10 , 7 , 14 ] , while our problem involves different k DPs executed over different graphs (split-graphs). The first step is to unify the split-graphs, which is not covered in the literature. Thus, we propose ShareDP , a batch- k DP algorithm that aims to share common computations and storage across a batch of k DP queries. The overall framework of ShareDP is illustrated in Fig. 2 (explained in Sec. 5.1 ). ShareDP incorporates the following key strategies: (1) We consolidate individual split-graphs into a unified structure, represented implicitly via result sets, simplifying construction and updates. (2) Using the merged split-graph, we enable concurrent k DP query processing by consolidating traversals and operations leveraging tagged data structures, reducing redundancy and improving efficiency. In summary, our contributions are: • Merged Split-Graph Representation. The ShareDP framework introduces a novel merged split-graph representation that consolidates individual split-graphs into a unified structure, enabling dynamic sharing of traversals. • Optimized Path-Finding with Shared Traversals. The framework combines traversals across multiple queries, consolidating common operations into single steps, reducing redundancy and improving efficiency. • Proven Efficiency and Scalability. Extensive evaluations on 12 real-world datasets demonstrate that ShareDP consistently achieves the lowest runtime across various k settings, confirming its efficiency and scalability. 2 Preliminaries We use p for a path and P for a set of paths. A vertex v is an intermediate vertex in path p if it is neither the starting nor the ending vertex. If v is intermediate in any path in P , it is called P -inner . A path p is simple if no vertex appears more than once. V(P) and E(P) refer to the set of vertices and edges that appear in at least one path in P . While the focus here is on directed graphs, the method can be easily adapted to undirected graphs. Disjoint Paths Given a graph G=(V,E) and two simple paths p_{1} and p_{2} from s to t , p_{1} and p_{2} are disjoint if they share no common vertex except s or t . Problem Statement Given a graph G=(V,E) , a parameter k , and a set of k DP queries Q=\{q_{0},q_{1},...,q_{\omega}\} where each query q_{i} is a vertex pair (s_{i},t_{i}) ( i=1,...,\omega ), batch- k DP is to find k disjoint paths for each query (s_{i},t_{i})\in Q . 3 Related Work 3.1 k DP problems Single-query. Approaches to single-query k DP can be divided into flow-augmenting path-based methods [ 4 , 13 , 5 ] and dissimilar path-based methods [ 8 , 2 , 11 ] . Flow-augmenting methods use split-graphs [ 4 , 5 ] , achieving linear time complexity (Sec. 4 ). Dissimilar path-based methods, which define dissimilarity as disjointness, include penalty-based , dissimilarity-based , and plateaus-based methods [ 8 , 11 ] . Plateaus-based methods, however, may fail to find solutions, as they depend on shared branches between two shortest spanning trees, which may not present in all k DP solutions. Thus, we exclude them from comparison. Penalty-based and dissimilarity-based methods reduce to path enumeration with disjointness constraints, either by (1) marking vertices in previous paths as inaccessible or by (2) verifying disjointness before adding new paths. However, both lead to factorial time complexity in the worst case. For instance, if a path p is not part of

Read the complete text