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 |V | = n and |E| = m, in o(m) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+) approximation in O(log n/2) amortized time per update. For maximum matching, we show how to maintain a (3+) approximation in O(min(n/, m1/3/2) amortized time per update and a (4 + ) approximation in O(m1/3/2) 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 [in 42nd ACM Symposium on Theory of Computing, Cambridge, MA, ACM, 2010, pp. 457–464].