Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching in a fully dynamic graph $G=(V,E)$, with $\mathrm{\mid }V\mathrm{\mid }=n$ and $\mathrm{\mid }E\mathrm{\mid }=m$, in $o(\sqrt{m})$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+\text{eps})$ approximation in $O(\log n\mathrm{/}{\text{eps}}^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+\text{eps})$ approximation in $O(\min (\sqrt{n}\mathrm{/}ϵ,m^{1\mathrm{/}3}\mathrm{/}{\text{eps}}^2))$ {\em amortized} time per update, and a $(4+\text{eps})$ approximation in $O(m^{1\mathrm{/}3}\mathrm{/}{\text{eps}}^2)$ {\em worst-case} time per update. Our data structure for fully dynamic minimum vertex cover is essentially near-optimal and settles an open problem by Onak and Rubinfeld from STOC’ 2010.