hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
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 $\mu(G)$. We define a
dynamic matching algorithm to be $\alpha$ (respectively $(\alpha,
\beta)$)-approximate if it maintains matching $M$ such that at all times $|M |
\geq \mu(G) \cdot \alpha$ (respectively $|M| \geq \mu(G) \cdot \alpha -
\beta$).
We present the first deterministic $(1-\epsilon )$-approximate dynamic
matching algorithm with $O(poly(\epsilon ^{-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/\epsilon $
[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, \epsilon \cdot 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-\epsilon )$-approximate
dynamic matching allowing for updates both increasing and decreasing the
maximum matching size of $G$ in a fully dynamic manner.
