Deterministic fully dynamic data structures for vertex cover and matching

DOI10.1137/140998925zbMATH Open1390.05221arXiv1412.1318OpenAlexW2809141942WikidataQ129639090 ScholiaQ129639090MaRDI QIDQ4571920FDOQ4571920

Authors: Sayan Bhattacharya, Giuseppe F. Italiano, Monika R. Henzinger 

Publication date: 4 July 2018

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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(sqrtm,)$ time per update. In particular, for minimum vertex cover we provide deterministic data structures for maintaining a $(2+eps)$ approximation in $O(logn/ep{s}^2)$ amortized time per update. For maximum matching, we show how to maintain a $(3+eps)$ approximation in $O(min(sqrtn/epsilon,m^{1/3}/ep{s}^2))$ {em amortized} time per update, and a $(4+eps)$ approximation in $O(m^{1/3}/ep{s}^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.

Full work available at URL: https://arxiv.org/abs/1412.1318

Recommendations

• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Dynamic approximate vertex cover and maximum matching
• Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
• Deterministic dynamic matching in \(O(1)\) update time

zbMATH Keywords

dynamic data structuresmaximum matchingprimal-dual methodfully dynamic algorithmsminimum vertex conver

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Faster scaling algorithms for general graph matching problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Linear-time approximation for maximum weight matching
• Online and dynamic algorithms for set cover
• Faster dynamic matchings and vertex connectivity
• Maintaining a large matching and a small vertex cover
• Fully Dynamic Maximal Matching in O (log n) Update Time
• Fully dynamic matching in bipartite graphs
• Faster fully dynamic matchings with small approximation ratios
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
• Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
• New deterministic approximation algorithms for fully dynamic matching

Cited In (15)

• Title not available (Why is that?)
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Dynamic approximate vertex cover and maximum matching
• Approximating multistage matching problems
• Dominating sets and connected dominating sets in dynamic graphs
• Approximating multistage matching problems
• Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
• Deterministic fully dynamic data structures for vertex cover and matching
• Dynamic Matching Algorithms in Practice
• Fully dynamic maintenance of vertex cover
• Deterministically maintaining a \((2 + \epsilon)\)-approximate minimum vertex cover in \(O(1/\epsilon^2)\) amortized update time
• Deterministic dynamic matching in worst-case update time
• Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
• On regularity lemma and barriers in streaming and dynamic matching
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time

This page was built for publication: Deterministic fully dynamic data structures for vertex cover and matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4571920)