Beating the Folklore Algorithm for Dynamic Matching
share
The maximum matching problem in dynamic graphs subject to edge updates (insertions and deletions) has received much attention over the last few years; a multitude of approximation/time tradeoffs were obtained, improving upon the folklore algorithm, which maintains a maximal (and hence 2-approximate) matching in O(n) worst-case update time in n-node graphs. We present the first deterministic algorithm which outperforms the folklore algorithm in terms of both approximation ratio and worst-case update time. Specifically, we give a (2-Ω(1))-approximate algorithm with O(√(n)√(m))=O(n^3/4) worst-case update time in n-node, m-edge graphs. For sufficiently small constant ϵ>0, no deterministic (2+ϵ)-approximate algorithm with worst-case update time O(n^0.99) was known. Our second result is the first deterministic (2+ϵ)-approximate (weighted) matching algorithm with O_ϵ(1)· O(√(m)) = O_ϵ(1)· O(√(n)) worst-case update time.
READ FULL TEXT