English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time

MPS-Authors
/persons/resource/persons285340

Kiss,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

2302.05030v3.pdf
(Preprint), 632KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bhattacharya, S., Kiss, P., & Saranurak, T. (2023). Dynamic (1+ϵ)-Approximate Matching Size in Truly Sublinear Update Time. Retrieved from https://arxiv.org/abs/2302.05030.


Cite as: https://hdl.handle.net/21.11116/0000-000C-9BA8-8
Abstract
We show a fully dynamic algorithm for maintaining $(1+\epsilon)$-approximate
\emph{size} of maximum matching of the graph with $n$ vertices and $m$ edges
using $m^{0.5-\Omega_{\epsilon}(1)}$ update time. This is the first polynomial
improvement over the long-standing $O(n)$ update time, which can be trivially
obtained by periodic recomputation. Thus, we resolve the value version of a
major open question of the dynamic graph algorithms literature (see, e.g.,
[Gupta and Peng FOCS'13], [Bernstein and Stein SODA'16],[Behnezhad and Khanna
SODA'22]).
Our key technical component is the first sublinear algorithm for $(1,\epsilon
n)$-approximate maximum matching with sublinear running time on dense graphs.
All previous algorithms suffered a multiplicative approximation factor of at
least $1.499$ or assumed that the graph has a very small maximum degree.