Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs

An efficient parallel algorithm for testing whether a graph G is k-vertex connected is presented. The algorithm runs in O(k² log n) time and uses (n + k²) kC (n, m) processors on a CRCW PRAM, where n and m are the number of vertices and edges of G, and C(n, m) is the number of processors required to compute the connected components of G in logarithmic time. For fixed k, the algorithm runs in logarithmic time and uses nC(n, m) processors. To develop our algorithm, an efficient parallel algorithm is designed for the following disjoint s-t paths problem. Given a graph G, and two specified vertices s and t, find k vertex disjoint paths between s and t, if they exist. If no such paths exist, find a set of at most k - 1 vertices whose removal disconnects s and t. The parallel algorithm for this problem runs in O(k² log n) time and uses kC(n, m) processors. The way to modify the algorithm to find k-edge disjoint paths, if they exist, is shown. This yields an efficient parallel algorithm for testing whether a graph G is k-edge connected. The algorithm runs in O(k² log n) time and uses nkC(n, kn) processors on a CRCW PRAM. Finally, more applications of the disjoint s-t paths algorithm are described.