Scan-first search and sparse certificates. An improved parallel algorithm for k-vertex connectivity

Given a graph G = (V,E), a certificate of k-vertex connectivity is an edge subset E′ ⊃ E such that the subgraph (V, E′) is k-vertex connected if and only if G is k-vertex connected. Let n and m denote the number of vertices and edges. A certificate is called sparse if it contains O(kn) edges. For undirected graphs, this paper introduces a graph search called the scan-first search, and shows that a certificate with at most k(n - 1) edges can be computed by executing scan-first search k times in sequence on subgraphs of G. For each of the parallel, distributed, and sequential models of computation, the complexity of scan-first search matches the best complexity of any graph search on that model. In particular, the parallel scan-first search runs in O(log n) time using C(n, m) processors on a CRCW PRAM, where C(n, m) is the number of processors needed to find a spanning tree in each connected component in O(log n) time, and the parallel certificate algorithm runs in O(k log n) time using C(n, m) processors. The parallel certificate algorithm can be employed to test the k-vertex connectivity of an undirected graph in O(k² log n) time using knC(n, kn) processors on a CRCW PRAM. For all combinations of n, m, and k > 3, both the tunning time and the number of processors either improve on or match those of all known deterministic parallel algorithms. This paper also obtains an online algorithm for computing an undirected graph certificate with at most 2kn edges, and a sequential algorithm for computing a directed graph certificate with at most 2k²n edges.