Decremental Matching in General Graphs

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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 [29]) gave an algorithm for this problem with an update time of O(√m/ε2). Motivated by the fact that the Oε(√m) barrier is hard to overcome (see Henzinger, Krinninger, Nanongkai, and Saranurak [30]; Kopelowitz, Pettie, and Porat [34]), we study this problem in the decremental model, where the adversary is only allowed to delete edges. Recently, Bernstein, Probst-Gutenberg, and Saranurak (see [9]) 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 [26] 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.

Original languageEnglish (US)
Title of host publication49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
EditorsMikolaj Bojanczyk, Emanuela Merelli, David P. Woodruff
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772358
DOIs
StatePublished - Jul 1 2022
Event49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022 - Paris, France
Duration: Jul 4 2022Jul 8 2022

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume229
ISSN (Print)1868-8969

Conference

Conference49th EATCS International Conference on Automata, Languages, and Programming, ICALP 2022
Country/TerritoryFrance
CityParis
Period7/4/227/8/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamic algorithms
  • matching
  • primal-dual algorithms

Cite this