Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time

被引:0
作者
Bhattacharya, Sayan [1 ]
Kiss, Peter [2 ]
Urak, Thatchaphol saran [3 ]
Wajc, David [4 ]
机构
[1] Univ Warwick, Coventry, England
[2] Univ Warwick, Dept Comp Sci, Coventry, England
[3] Univ Michigan, Ann Arbor, MI USA
[4] Technion Israel Inst Technol, Haifa, Israel
基金
英国工程与自然科学研究理事会;
关键词
Dynamic algorithms; approximate matching; MINIMUM VERTEX COVER; MAXIMUM; ALGORITHMS;
D O I
10.1145/3679009
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
We present dynamic algorithms with polylogarithmic update time for estimating the size of the maximum matching of a graph undergoing edge insertions and deletions with approximation ratio strictly better than 2. Specifically, we obtain a 1+ root 21 + & varepsilon; approximate to 1.707+& varepsilon; approximation in bipartite graphs and a 1.973+& varepsilon; approximation in general graphs. We thus answer in the affirmative the value version of the major open question repeatedly asked in the dynamic graph algorithms literature. Our randomized algorithms' approximation and worst-case update time bounds both hold w.h.p. against adaptive adversaries. Our algorithms are based on simulating new two-pass streaming matching algorithms in the dynamic setting. Our key new idea is to invoke the recent sublinear-time matching algorithm of Behnezhad (FOCS'21) in a white-box manner to efficiently simulate the second pass of our streaming algorithms, while bypassing the well-known vertex-update barrier.
引用
收藏
页数:32
相关论文
共 84 条
[1]   Popular Conjectures as a Barrier for Dynamic Planar Graph Algorithms [J].
Abboud, Amir ;
Dahlgaard, Soren .
2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, :477-486
[2]   Popular conjectures imply strong lower bounds for dynamic problems [J].
Abboud, Amir ;
Williams, Virginia Vassilevska .
2014 55TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2014), 2014, :434-443
[3]   Linear programming in the semi-streaming model with application to the maximum matching problem [J].
Ahn, Kook Jin ;
Guha, Sudipto .
INFORMATION AND COMPUTATION, 2013, 222 :59-79
[4]  
[Anonymous], 2013, P 30 INT S THEOR ASP
[5]  
Arar Moab, 2018, P 45 INT C AUT LANG, V79, P1
[6]  
Assadi S, 2024, Arxiv, DOI [arXiv:2406.13573, DOI 10.48550/ARXIV.2406.13573]
[7]   On Regularity Lemma and Barriers in Streaming and Dynamic Matching [J].
Assadi, Sepehr ;
Behnezhad, Soheil ;
Khanna, Sanjeev ;
Li, Huan .
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, :131-144
[8]  
Assadi S, 2022, PROCEEDINGS OF THE 2022 ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SODA, P627
[9]   The Stochastic Matching Problem with (Very) FewQueries [J].
Assadi, Sepehr ;
Khanna, Sanjeev ;
Li, Yang .
ACM TRANSACTIONS ON ECONOMICS AND COMPUTATION, 2019, 7 (03)
[10]  
Assadi Sepehr., 2016, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, P1345