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 R(k-1), f:V --> R(k-1), such that no hyperplane contains k points of {f(v)\v is-an-element-of V}, and for each v is-an-element-of V - X, f(v) is in the convex hull of {f(w)\(v, w) is-an-element-of E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lovasz and Wigderson in ''Rubber bands, convex embeddings and graph connectivity,'' Combinatorica 8 (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)).(logn)) 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 x 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 k = square-root n, 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.