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

Joseph Cheriyan*, Ming Yang Kao, Ramakrishna Thurimella

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

54 Scopus citations


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(k2 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 2k2n edges.

Original languageEnglish (US)
Pages (from-to)154-174
Number of pages21
JournalSIAM Journal on Computing
Issue number1
StatePublished - 1993

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'Scan-first search and sparse certificates. An improved parallel algorithm for k-vertex connectivity'. Together they form a unique fingerprint.

Cite this