Dynamic (1 + ε)-approximate matchings: a density-sensitive approach
David Peleg, Shay Solomon · Symposium on Discrete Algorithms · 2016
Approximate matchings in fully dynamic graphs have been intensively studied in recent years. Cupta and Peng [FOCS'13] presented a deterministic algorithm for maintaining fully dynamic (1 + e)-approximate maximum cardinality matching (MCM) in general graphs with worst-case update time O([EQUATION]), for any e > 0, where m denotes the current number of edges in the graph. Despite significant research efforts, this [EQUATION] update time barrier remains the state-of-the-art even if amortized time bounds and randomization are allowed or the approximation factor is allowed to increase from 1 + e to 2 -- e, and even in basic graph families such as planar graphs.This paper presents a simple deterministic algorithm whose performance depends on the density of the graph. Specifically, we maintain fully dynamic (1 + e)-approximate MCM with worst-case update time O(α ·e--2) for graphs with arboricity1 bounded by α. The update time bound holds even if the arboricity bound α changes dynamically. Since the arboricity ranges between 1 and [EQUATION], our density-sensitive bound O(α · e--2) naturally generalizes the O([EQUATION] · e--2) bound of Gupta and Peng.For the family of bounded arboricity graphs (which includes forests, planar graphs, and graphs excluding a fixed minor), in the regime e = O(1) our update time reduces to a constant. This should be contrasted with the previous best 2-approximation results for bounded arboricity graphs, which achieve either an O(log n) worst-case bound (Kopelowitz et al., ICALP'14) or an O([EQUATION]) amortized bound (He et al., ISAAC'14), where n stands for the number of vertices in the graph.En route to this result, we provide local algorithms of independent interest for maintaining fully dynamic approximate matching and vertex cover.