Deterministic fully dynamic data structures for vertex cover and matching

DOI10.1137/140998925MaRDI QIDQ4571920zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

dynamic data structuresfully dynamic algorithmsmaximum matchingminimum vertex converprimal-dual method

Mathematics Subject Classification ID

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

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.

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(^3 n) worst case update time
• Deterministic dynamic matching in \(O(1)\) update time

Cites work

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

Cited in

(17)

• 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(^3 n) worst case update time
• Dynamic approximate vertex cover and maximum matching
• Dominating sets and connected dominating sets in dynamic graphs
• Fault tolerant and fully dynamic DFS in undirected graphs: simple yet efficient
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
• Deterministic fully dynamic data structures for vertex cover and matching
• Dynamic Matching Algorithms in Practice
• Approximating multistage matching problems
• Approximating multistage matching problems
• Deterministic dynamic matching in worst-case update time
• Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
• Fully dynamic maintenance of vertex cover
• On regularity lemma and barriers in streaming and dynamic matching
• On solution discovery via reconfiguration
• Dynamic matching with better-than-2 approximation in polylogarithmic 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)