Article

Faster dynamic matchings and vertex connectivity

Author:

Piotr SankowskiAuthors Info & Claims

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

Pages 118 - 126

Published: 07 January 2007 Publication History

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. In SODA '93: Proceedings of the fourth annual ACMSIAM Symposium on Discrete algorithms, pages 31--40, Philadelphia, PA, USA, 1993. Society for Industrial and Applied Mathematics.

Digital Library

[3]

Joseph Cheriyan and John H. Reif. Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity. In SODA '92: Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, pages 335--344, Philadelphia, PA, USA, 1992. Society for Industrial and Applied Mathematics.

Digital Library

[4]

D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. In Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 1--6. ACM Press, 1987.

Digital Library

[5]

J. Edmonds and R. M. Karp. Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. J. ACM, 19(2):248--264, 1972.

Digital Library

[6]

David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification--a technique for speeding up dynamic graph algorithms. J. ACM, 44(5):669--696, 1997.

Digital Library

[7]

H. N. Gabow. Using expander graphs to find vertex connectivity. In FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, page 410, Washington, DC, USA, 2000. IEEE Computer Society.

Digital Library

[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, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723--760, 2001.

Digital Library

[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]

M.-Y. Kao, T. W. Lam, W.-K. Sung, and H.-F. Ting. A decomposition theorem for maximum weight bipartite matchings with applications to evolutionary trees. In Proceedings of the 7th Annual European Symposium on Algorithms, pages 438--449, 1999.

Digital Library

[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]

K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. In STOC '87: Proceedings of the nineteenth annual ACM conference on Theory of computing, pages 345--354. ACM Press, 1987.

Digital Library

[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. In Proceedings of the 45th annual IEEE Symposium on Foundations of Computer Science, pages 248--255, 2004.

Digital Library

[17]

J. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27:701--717, 1980.

Digital Library

[18]

R. Zippel. Probabilistic algorithms for sparse polynomials. In International Symposium on Symbolic and Algebraic Computation, volume 72 of Lecture Notes in Computer Science, pages 216--226, Berlin, 1979. Springer-Verlag.

Digital Library

Cited By

Chen JCzerwiński WDisser YFeldmann AHermelin DNadara WPilipczuk MPilipczuk MSorge MWróblewski BZych-Pawlewicz AMarx D(2021)Efficient fully dynamic elimination forests with applications to detecting long paths and cyclesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458114(796-809)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458114
Bernstein AForster SHenzinger MChan T(2019)A deamortization approach for dynamic spanner and dynamic maximal matchingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310550(1899-1918)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310550
Grandoni FLeonardi SSankowski PSchwiegelshohn CSolomon SChan T(2019)(1 + ε-Approximate incremental matching in constant deterministic amortized timeProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310549(1886-1898)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310549
Show More Cited By

Faster dynamic matchings and vertex connectivity
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation

Recommendations

Matchings in 3-vertex-critical graphs: The odd case

A subset of vertices D of a graph G is a dominating set for G if every vertex of G not in D is adjacent to one in D. The cardinality of any smallest dominating set in G is denoted by @c(G) and called the domination number of G. Graph G is said to be @c-...
Super-Connectivity and Hyper-Connectivity of Vertex Transitive Bipartite Graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if the deletion of each minimum vertex cut creates exactly two components, one of which is an isolated vertex. In this note, we ...
Connectivity of vertex and edge transitive graphs

A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if each minimum vertex cut creates exactly two components, one of which is an isolated vertex. It is proved that a connected ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '07: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms

January 2007

1322 pages

ISBN:9780898716245

Conference Chair:
Harold Gabow
University of Colorado, Boulder

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 07 January 2007

Check for updates

Qualifiers

Article

Acceptance Rates

SODA '07 Paper Acceptance Rate 139 of 382 submissions, 36%;

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
867
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)5

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JCzerwiński WDisser YFeldmann AHermelin DNadara WPilipczuk MPilipczuk MSorge MWróblewski BZych-Pawlewicz AMarx D(2021)Efficient fully dynamic elimination forests with applications to detecting long paths and cyclesProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458114(796-809)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458114
Bernstein AForster SHenzinger MChan T(2019)A deamortization approach for dynamic spanner and dynamic maximal matchingProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310550(1899-1918)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310550
Grandoni FLeonardi SSankowski PSchwiegelshohn CSolomon SChan T(2019)(1 + ε-Approximate incremental matching in constant deterministic amortized timeProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310549(1886-1898)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310549
Datta SKulkarni RMukherjee ASchwentick TZeume T(2018)Reachability Is in DynFOJournal of the ACM10.1145/321268565:5(1-24)Online publication date: 29-Aug-2018
https://dl.acm.org/doi/10.1145/3212685
Bosek BLeniowski DSankowski PZych-Pawlewicz A(2018)Shortest Augmenting Paths for Online Matchings on TreesTheory of Computing Systems10.1007/s00224-017-9838-x62:2(337-348)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s00224-017-9838-x
Bhattacharya SHenzinger MNanongkai DKlein P(2017)Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update timeProceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3039686.3039716(470-489)Online publication date: 16-Jan-2017
https://dl.acm.org/doi/10.5555/3039686.3039716
Gupta AKrishnaswamy RKumar APanigrahi DHatami HMcKenzie PKing V(2017)Online and dynamic algorithms for set coverProceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3055399.3055493(537-550)Online publication date: 19-Jun-2017
https://dl.acm.org/doi/10.1145/3055399.3055493
Kopelowitz TPettie SPorat E(2016)Higher lower bounds from the 3SUM conjectureProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884524(1272-1287)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884524
Peleg DSolomon S(2016)Dynamic (1 + ε)-approximate matchingsProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884486(712-729)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884486
Bernstein AStein C(2016)Faster fully dynamic matchings with small approximation ratiosProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884485(692-711)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884485
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents