Faster fully dynamic matchings with small approximation ratios

Maximum cardinality matching is a fundamental algorithmic problem with many algorithms and applications. The fully dynamic version, in which edges are inserted and deleted over time has also been the subject of much attention. Existing algorithms for dynamic matching (in general n-vertex m-edge graphs) fall into two groups: there are fast (mostly randomized) algorithms that achieve a 2-approximation or worse, and there are slow algorithms with Ω(√m) update time that achieve a better-than-2 approximation. Thus the obvious question is whether we can design an algorithm that achieves a tradeoff between these two: a o(√m) update time and a better-than-2 approximation simultaneously. We answer this question in the affirmative. Previously, such bounds were only known for the special case of bipartite graphs. Our main result is a fully dynamic deterministic algorithm that maintains a (3/2 + ϵ)-approximation in amortized update time O(m^1/4ϵ-2.5). In addition to achieving the trade-off described above, our algorithm manages to be polynomially faster than all existing deterministic algorithms (excluding an existing log n-approximation of Onak and Rubinfeld), while still maintaining a better-than-2 approximation. We also give stronger results for graphs whose arboricity is at most α. We show how to maintain a (1 + α)-approximate fractional matching or a (3/2 + ϵ)-approximate integral matching in worst-case time O(α(α + logn)) for constant ϵ. When the arboricity is constant, this bound is O(logn) and when the arboricity is polylogarithmic the update time is also polylogarithmic. Previous results for small arboricity non-bipartite graphs could only maintain a maximal matching (2-approximation). We maintain the approximate matching without explicitly using augmenting paths. We define an intermediate graph, called an EDCS and show that the EDCS H contains a large matching, and show how to maintain an EDCS in G. The EDCS was used in previous works on bipartite graphs, however the details and proofs are completely different in general graphs. The algorithm for bipartite graphs relies on ideas from flows and cuts to non-constructively prove the existence of a good matching in H, but these ideas do not seem to extend to non-bipartite graphs. In this paper we instead explicitly construct a large fractional matching in H. In some cases we can guarantee that this fractional matching is γ-restricted, which means that it only uses values either in the range [0,γ] or 1. We then combine this matching with a new structural property of maximum matchings in nonbipartite graphs, which is analogous to the cut induced by maximum matchings in bipartite graphs.