Faster dynamic matchings and vertex connectivity

ABSTRACT

We present first fully dynamic subquadratic algorithms for: computing maximum matching size, computing maximum bipartite matching weight, computing maximum number of vertex disjoint s, t paths and testing directed vertex k-connectivity of the graph. The presented algorithms are randomized. The algorithms for maximum matching size and disjoint paths support operations in O(n^1.495) time. The algorithm for computing the maximum bipartite matching weight maintains the graph with integer edge weights from the set 1,..., W in O(W^2.495n^1.495) time. The algorithm for testing directed vertex k-connectivity supports updates in O(n^1.575 + nk²) time. For all of these problems the presented dynamic algorithms break the input size barrier --- O(n²).

As a side result we obtain a dynamic algorithm for the dynamic maintenance of the rank of the matrix that support updates in O(n^1.495) time.

REFERENCES

• 1: M. Becker, W. Degenhardt, J. Doenhardt, S. Hertel, G. Kaninke, W. Keber, K. Mehlhorn, S. Naher, H. Rohnert, and T. Winter. A probabilistic algorithm-for vertex connectivity of graph. Information Processing Letters, 15:135--136, 1982.
• 2: Joseph Cheriyan, Random Weighted Laplacians, Lovász minimum digraphs and finding minimum separators, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.31-40, January 25-27, 1993, Austin, Texas, United States
• 3: Joseph Cheriyan , John H. Reif, Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.335-344, September 1992, Orlando, Florida, United States
• 4: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• 5: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 6: David Eppstein , Zvi Galil , Giuseppe F. Italiano , Amnon Nissenzweig, Sparsification—a technique for speeding up dynamic graph algorithms, Journal of the ACM (JACM), v.44 n.5, p.669-696, Sept. 1997 [doi>10.1145/265910.265914]
• 7: H. N. Gabow, Using expander graphs to find vertex connectivity, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.410, November 12-14, 2000
• 8: Peter Frands Frandsen Gudmund Skovbjerg Frandsen. Dynamic matrix rank. Lecture Notes in Computer Science, 4051:395--406, 2006.
• 9: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001 [doi>10.1145/502090.502095]
• 10: W. Morrison J. Sherman. Adjustment of an inverse matrix corresponding to changes in the elements of a given column or a given row of the original matrix. Ann. Math. Statist., 20:621--, 1949.
• 11: Ming-Yang Kao , Tak Wah Lam , Wing-Kin Sung , Hing-Fung Ting, A Decomposition Theorem for Maximum Weight Bipartite Matchings with Applications to Evolutionary Trees, Proceedings of the 7th Annual European Symposium on Algorithms, p.438-449, July 16-18, 1999
• 12: L. Lovász. On determinants, matchings and random algorithms. In L. Budach, editor, Fundamentals of Computation Theory, pages 565--574. Akademie-Verlag, 1979.
• 13: K. Mehlhorn. Data Structures and Algorithms 2: Graph Algorithms and NP-Completeness. Springer-Verlag, Berlin, 1984.
• 14: Ketan Mulmuley , Umesh V. Vazirani , Vijay V. Vazirani, Matching is as easy as matrix inversion, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.345-354, January 1987, New York, New York, United States [doi>10.1145/28395.383347]
• 15: L. Lovász N. Linial and A. Wigderson. Rubber bands, convex embeddings and graph connectivity. Combinatorica, 8:91--102, 1988.
• 16: Piotr Sankowski, Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.509-517, October 17-19, 2004 [doi>10.1109/FOCS.2004.25]
• 17: 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]
• 18: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979