Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity

\indent Given a graph $G = (V,E)$ with $n$ vertices and $m$ edges, a {\em certificate} of $k$-vertex connectivity is an edge subset $E'' \subset E$ such that the subgraph $(V,E'')$ is $k$-vertex connected if and only if $G$ is $k$-vertex connected. A certificate is called {\em sparse} if it contains $O(kn)$ edges. Our main result is an algorithm that computes a sparse certificate with at most $kn$ edges for an {\em undirected} graph. The key technique used in our certificate algorithm is a novel graph search strategy called the {\em scan-first search}. Both this search strategy and our certificate algorithm have extremely efficient implementations in the sequential, distributed, and parallel models of computation. In particular, our certificate algorithm runs in $O(k \, \mbox {log} \, n)$ time using $C(n,m)$ processors on a CRCW PRAM, where $C(n,m)$ is the number of processors used to compute a spanning tree in each connected component in $O(\mbox{log} \, n)$ time. Our parallel certificate algorithm can be employed to test the $k$-vertex connectivity of an undirected graph in $O(k^{2} \, \mbox{log} \, n)$ time using $k \cdot n \cdot C(n,kn)$ processors on a CRCW PRAM. This parallel complexity is substantially better than several previously best results for undirected $k$-vertex connectivity. Using different techniques, we also obtain 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^{2}n$ edges.