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: https://drops.dagstuhl.de/opus/volltexte/2023/18675/
Go to the corresponding LIPIcs Volume Portal


Blikstad, Joakim ; Kiss, Peter

Incremental (1-ε)-Approximate Dynamic Matching in O(poly(1/ε)) Update Time

pdf-format:
LIPIcs-ESA-2023-22.pdf (0.9 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI