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

ABSTRACT

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 &rarr:Rk-1, such that no hyperplane contains k points of {f(v) | v &egr; V}, and for each v &egr; V - X, f(v) is in the convex hull of {f(w) | (v, w) &egr; E}. This result generalizes to directed graphs the notion of convex embeddings of undirected graphs introduced by Linial, Lova´sz 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)).(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 x n matrices (M(n) = O(n2.3755)). Our Monte Carlo algorithm improves on the best previous deterministic and randomized time complexities for k > n0.19; e.g., for k = (n0.5, 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.

REFERENCES

• B 82: M. Becker, W. Degenhardt, J. Doenhardt, S. Hertel, G. Kaninke, W. Keber, K. Mehlhorn, S. N~her, H. Rohnert, and T. Winter, "A probabilistic algorithm for vertex connectivity of graphs", Information Processing Letters 15 (1982), 135-136.
• B 78: Bela Bollobas, Extremal Graph Theory, Dover Publications, Incorporated, 2004
• CM 88: J. Cheriyan , S. N. Maheshwari, Finding nonseparating induced cycles and independent spanning trees in 3-connected graphs, Journal of Algorithms, v.9 n.4, p.507-537, Dec. 1988 [doi>10.1016/0196-6774(88)90015-6]
• CKT 91: Joseph Cheriyan , Ming-Yang Kao , Ramakrishna Thurimella, Scan-first search and sparse certificates: an improved parallel algorithm for k-vertex connectivity, SIAM Journal on Computing, v.22 n.1, p.157-174, Feb. 1993 [doi>10.1137/0222013]
• CW 87: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• E 75: S. Even, "An Algorithm for Determining Whether the Connectivity of a Graph is at Least k," SIAM J. Computing 4 (1975), 303-396.
• E 79: Shimon Even, Graph Algorithms, W. H. Freeman & Co., New York, NY, 1979
• G 80: g. Galil, "Finding the vertex connectivity of graphs," SIAM J. Computing 9 (1980), 197-199.
• IR 88: Alon Itai , Michael Rodeh, The multi-tree approach to reliability in distributed networks, Information and Computation, v.79 n.1, p.43-59, October 1988 [doi>10.1016/0890-5401(88)90016-8]
• KP 91: Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States [doi>10.1145/113379.113396]
• LEC 66: A. Lempel, S. Even and I. Cederbaum, "An algorithm for planarity testing of graphs." In Theory of Graphs: Internat. Sympos.: Rome P. Rosenstiehl, Ed., 215-232, Gordon and Breach, New York, 1966.
• LLW 88: N. Linlal, L. Lov~sz and A. Wigderson, "Rubber bands, convex embeddings and graph connectivity," Combinatorica 8 (1988), 91-102.
• Lo 73: L. Lov~sz, "Connectivity in Digraphs", J. Combinatorial Theory (B) 15 (1973), 174-177.
• Lo 79: L. Lovf~sz, Combinatorial Problems and Exercises, North-Holland, 1979.
• LSS 89: L. Lov~sz, M. Saks, and A. Schrijver, "Orthogonal representations and connectivity of graphs", Linear Algebra and its Applications 114/115 (1989), 439-454.
• M 84: Kurt Mehlhorn, Graph algorithms and NP-completeness, Springer-Verlag New York, Inc., New York, NY, 1984
• MVV 87: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• NI 90: H. Nagamochi and T. Ibaraki, "Linear Time Algorithms for Finding a Sparse k-Connected Spanning Subgraph of a k-Connected Graph", Algorithmica, to appear. "Linear time algorithms for finding k-edge-connected and k-node-connected spanning subgraphs", Technical Report #89006, Dept. of Applied Mathematics & Physics, Faculty of Engineering, Kyoto University, 1989.
• P 87: V. Pan, Complexity of parallel matrix computations, Theoretical Computer Science, v.54 n.1, p.65-85, 1987 [doi>10.1016/0304-3975(87)90019-3 ]
• P 91: J. Plehn, Ph.D. Thesis, University of Bonn, Germany.
• S 79: A. Schrijver, "Fractional packing and covering." In Packing and Covering in Combinatorics, A. Schrijver, Ed., 201-274, Mathematisch Centrum, Amsterdam, 1979.
• Sc 80: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• W 87: R. W. Whitty, "Vertex-disjoint paths and edgedisjoint branchings in directed graphs" J. Graph Theory 11 (1987), 349-358.
• ZI 89: A. Zehavi and A. ItaJ, "Three tree-paths", J. Graph Theory 13 (1989), 175-188.
• Z 79: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification