External Memory Algorithms for Finding Disjoint Paths in Undirected Graphs

摘要

Consider the following well-known combinatorial problem: given an undirected graph G = (V, E), terminals s,t ? V, and an integer k ≥ 1, find k edge-disjoint s-t paths in G or report that such paths do not exist. We study this problem in the external memory (EM) model of Agrawal and Vitter, i.e. assume that only M words of random access memory (RAM) are available while the graph resides in EM, which enables reading and writing contiguous blocks of B words per single I/O. The latter external memory is also used for storing the output and some intermediate data. For k = 1, the problem consists in finding a single s-t path in an undirected graph and can be solved in Conn(V, E) = O ((V+E)/V Sort(V)log log (VB)/E) I/Os, where Sort(N) = O (N/B log_(M/B) N/B) is the complexity of sorting N words in external memory. Our contribution is two novel EM algorithms that solve the problem for k ≤M/B The first takes O(k · Conn(V, E)) I/Os. The second one applies the ideas of Ibaraki-Nagamochi sparse connectivity certificates and takes O ((Sort(V + E) + k · Conn(V, kV)) · log V/M) I/Os, which improves upon the first bound for sufficiently dense graphs. Both algorithms outperform the naive approach based on successive BFS- or DFS-augmentations for a wide range of parameters |V|, |E|, M, B.