License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2023.22
URN: urn:nbn:de:0030-drops-186756
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18675/
Blikstad, Joakim ;
Kiss, Peter
Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update Time
Abstract
In the dynamic approximate maximum bipartite matching problem we are given bipartite graph G undergoing updates and our goal is to maintain a matching of G which is large compared the maximum matching size μ(G). We define a dynamic matching algorithm to be α (respectively (α, β))-approximate if it maintains matching M such that at all times |M | ≥ μ(G) ⋅ α (respectively |M| ≥ μ(G) ⋅ α - β).
We present the first deterministic (1-ε)-approximate dynamic matching algorithm with O(poly(ε^{-1})) amortized update time for graphs undergoing edge insertions. Previous solutions either required super-constant [Gupta FSTTCS'14, Bhattacharya-Kiss-Saranurak SODA'23] or exponential in 1/ε [Grandoni-Leonardi-Sankowski-Schwiegelshohn-Solomon SODA'19] update time. Our implementation is arguably simpler than the mentioned algorithms and its description is self contained. Moreover, we show that if we allow for additive (1, ε⋅n)-approximation our algorithm seamlessly extends to also handle vertex deletions, on top of edge insertions. This makes our algorithm one of the few small update time algorithms for (1-ε)-approximate dynamic matching allowing for updates both increasing and decreasing the maximum matching size of G in a fully dynamic manner.
Our algorithm relies on the weighted variant of the celebrated Edge-Degree-Constrained-Subgraph (EDCS) datastructure introduced by [Bernstein-Stein ICALP'15]. As far as we are aware we introduce the first application of the weighted-EDCS for arbitrarily dense graphs. We also present a significantly simplified proof for the approximation ratio of weighed-EDCS as a matching sparsifier compared to [Bernstein-Stein], as well as simple descriptions of a fractional matching and fractional vertex cover defined on top of the EDCS. Considering the wide range of applications EDCS has found in settings such as streaming, sub-linear, stochastic and more we hope our techniques will be of independent research interest outside of the dynamic setting.
BibTeX - Entry
@InProceedings{blikstad_et_al:LIPIcs.ESA.2023.22,
author = {Blikstad, Joakim and Kiss, Peter},
title = {{Incremental (1-\epsilon)-Approximate Dynamic Matching in O(poly(1/\epsilon)) Update Time}},
booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)},
pages = {22:1--22:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-295-2},
ISSN = {1868-8969},
year = {2023},
volume = {274},
editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18675},
URN = {urn:nbn:de:0030-drops-186756},
doi = {10.4230/LIPIcs.ESA.2023.22},
annote = {Keywords: Bipartite Matching, Incremental Matching, Dynamic Algorithms, Approximation Algorithms, EDCS}
}
|
Keywords: |
|
Bipartite Matching, Incremental Matching, Dynamic Algorithms, Approximation Algorithms, EDCS |
|
Collection: |
|
31st Annual European Symposium on Algorithms (ESA 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
30.08.2023 |
