Directed s-t numberings, Rubber bands, and testing digraph k-vertex connectivity

Let G=(V, E) be a directed graph and n denote |V|. We show that G is k-vertex connected iff for every subset X of V with |X| =k, there is an embedding of G in the (k-1)-dimensional space Rk-1, f:V→Rk-1, such that no hyperplane contains k points of {f(v)|v∈V}, and for each v∈V-X, f(v) is in the convex hull of {f(w)| (v, w)∈E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovász and Wigderson in "Rubber bands, convex embeddings and graph connectivity", Combinatorica8 (1988), 91-102. Using this characterization, a directed graph can be tested for k-vertex connectivity by a Monte Carlo algorithm in time O((M(n)+nM(k)) · (log n)) with error probability<1/n, and by a Las Vegas algorithm in expected time O((M(n)+nM(k)) ·k), where M(n) denotes the number of arithmetic steps for multiplying two n×n matrices (M(n)=O(n2.376)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities for k>n0.19; e.g., for {Mathematical expression}, the factor of improvement is >n0.62. Both algorithms have processor efficient parallel versions that run in O((log n)2) time on the EREW PRAM model of computation, using a number of processors equal to log n times the respective sequential time complexities. Our Monte Carlo parallel algorithm improves on the number of processors used by the best previous (Monte Carlo) parallel algorithm by a factor of at least n2/(log n)3 while having the same running time. Generalizing the notion of s-t numberings, we give a combinatorial construction of a directed s-t numbering for any 2-vertex connected directed graph. © 1994 Akadémiai Kiadó.

Duke Scholars

Author John H. Reif Computer Science