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.ICALP.2022.11
URN: urn:nbn:de:0030-drops-163528
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16352/
Assadi, Sepehr ;
Bernstein, Aaron ;
Dudeja, Aditi
Decremental Matching in General Graphs
Abstract
We consider the problem of maintaining an approximate maximum integral matching in a dynamic graph G, while the adversary makes changes to the edges of the graph. The goal is to maintain a (1+ε)-approximate maximum matching for constant ε > 0, while minimizing the update time. In the fully dynamic setting, where both edge insertion and deletions are allowed, Gupta and Peng (see [Manoj Gupta and Richard Peng, 2013]) gave an algorithm for this problem with an update time of O(√m/ε²).
Motivated by the fact that the O_ε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [Henzinger et al., 2015]; Kopelowitz, Pettie, and Porat [Kopelowitz et al., 2016]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [Bernstein et al., 2020]) gave an O(poly({log n}/ε)) update time decremental algorithm for this problem in bipartite graphs. However, beating O(√m) update time remained an open problem for general graphs.
In this paper, we bridge the gap between bipartite and general graphs, by giving an O_ε(poly(log n)) update time algorithm that maintains a (1+ε)-approximate maximum integral matching under adversarial deletions. Our algorithm is randomized, but works against an adaptive adversary. Together with the work of Grandoni, Leonardi, Sankowski, Schwiegelshohn, and Solomon [Fabrizio Grandoni et al., 2019] who give an O_ε(1) update time algorithm for general graphs in the incremental (insertion-only) model, our result essentially completes the picture for partially dynamic matching.
BibTeX - Entry
@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11,
author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi},
title = {{Decremental Matching in General Graphs}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {11:1--11:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-235-8},
ISSN = {1868-8969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16352},
URN = {urn:nbn:de:0030-drops-163528},
doi = {10.4230/LIPIcs.ICALP.2022.11},
annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms}
}
Keywords: |
|
Dynamic algorithms, matching, primal-dual algorithms |
Collection: |
|
49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
28.06.2022 |