Deterministic fully dynamic approximate vertex cover and fractional matching in O(1) amortized update time

DOI10.1007/978-3-319-59250-3_8MaRDI QIDQ2401147zbMATH OpenOpenAlexFDO

Authors Sayan Bhattacharya, Deeparnab Chakrabarty, Monika R. Henzinger

Publication date 31 August 2017

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Abstract: We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld [STOC 2010], this problem has received significant attention in recent years. Very recently, extending the framework of Baswana, Gupta and Sen [FOCS 2011], Solomon [FOCS 2016] gave a randomized dynamic algorithm for this problem that has an approximation ratio of $2$ and an amortised update time of $O(1)$ with high probability. This algorithm requires the assumption of an {em oblivious adversary}, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm's past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in $O(1)$ update time. In this paper, we resolve this question. We present a new {em deterministic} fully dynamic algorithm that maintains a $O(1)$-approximate minimum vertex cover and maximum fractional matching, with an amortised update time of $O(1)$. Previously, the best deterministic algorithm for this problem was due to Bhattacharya, Henzinger and Italiano [SODA 2015]; it had an approximation ratio of $(2+epsilon)$ and an amortised update time of $O(logn/epsilo{n}^2)$. Our results also extend to a fully dynamic $O(f^3)$-approximate algorithm with $O(f^2)$ amortized update time for the hypergraph vertex cover and fractional hypergraph matching problems, where every hyperedge has at most $f$ vertices.

Recommendations

• Deterministic dynamic matching in \(O(1)\) update time
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministic fully dynamic data structures for vertex cover and matching
• Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time

Cited in

(20)

• Dynamic algorithms via the primal-dual method
• Approximating dynamic weighted vertex cover with soft capacities
• Deterministic dynamic matching in \(O(1)\) update time
• Deterministic fully dynamic data structures for vertex cover and matching
• Fully dynamic approximate maximum matching and minimum vertex cover in O(^3 n) worst case update time
• An \(o(1)\)-approximation algorithm for dynamic weighted vertex cover with soft capacity
• Optimal lower bounds for matching and vertex cover in dynamic graph streams
• Dynamic clustering to minimize the sum of radii
• Round compression for parallel matching algorithms
• Dynamic set cover: improved algorithms and lower bounds
• 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
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)
• Dynamic Matching Algorithms in Practice
• Deterministic dynamic matching in worst-case update time
• Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Fully dynamic maintenance of vertex cover
• Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
• Deterministic rounding of dynamic fractional matchings

This page was built for publication: Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time

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