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 vertical bar V vertical bar = n and vertical bar E vertical bar = m, in o(root m) time per update. In particular, for minimum vertex cover, we provide deterministic data structures for maintaining a (2+epsilon) approximation in O(log n/epsilon(2)) amortized time per update. For maximum matching, we show how to maintain a (3+epsilon) approximation in O(min(root n/epsilon m(1/3)/epsilon(2)) amortized time per update and a (4 + epsilon) approximation in O(m1/3/epsilon(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].