Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching

Original · EN

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(n/²) amortized time per update. For maximum matching, we show how to maintain a (3+) approximation in O((√n/ε, m¹/³/²)) amortized time per update, and a (4+) approximation in O(m¹/³/²) 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.