Abstract. 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/ , m 1/3 / 2 ) amortized time per update and a (4 + ) approximation in O(m 1/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]. Key words. fully dynamic algorithms, minimum vertex conver, maximum matching, dynamic data structures, primal-dual method AMS subject classification. 05C85 DOI. 10.1137/140998925 1. Introduction. Finding maximum matchings and minimum vertex covers in undirected graphs are classical problems in combinatorial optimization. Let G = (V, E) be an undirected graph, with m = |E| edges and n = |V | nodes. A matching in G is a set of vertex-disjoint edges; i.e., no two edges share a common vertex. A maximum matching, also known as maximum cardinality matching, is a matching with the largest possible number of edges. A matching is maximal if it is not a proper subset of any other matching in G. A subset V ⊆ V is a vertex cover if each edge of G is incident to at least one vertex in V . A minimum vertex cover is a vertex cover of smallest possible size. The Micali-Vazirani algorithm for maximum matching runs in O(m √ n ) time [13, 18] . Using this algorithm, a (1 + )-approximate maximum matching can be constructed in O(m/ ) time [8] . The same bound can also be obtained using scaling algorithms [9, 10] . Finding a minimum vertex cover, on the other hand, is NP-hard. Still, these two problems remain closely related as their LP-relaxations are duals of each other. Furthermore, a maximal matching, which can be computed in O(m) time in a greedy fashion, is known to provide a 2-approximation both to maximum matching and to minimum vertex cover (by using the endpoints of the maximal matching).
Bhattacharya et al. REF showed a deterministic (4 + ε)-approximation in O(m 1/3 /ε 2 ) worst-case update time.
Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
SIAM J. Comput.
SIAM J. Comput.
Computer Science Mathematics