Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach

Sepehr Assadi, Shay Solomon

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In the (fully) dynamic set cover problem, we have a collection of m sets from a universe of size n that undergo element insertions and deletions; the goal is to maintain an approximate set cover of the universe after each update. We give an O(f2) update time algorithm for this problem that achieves an f-approximation, where f is the maximum number of sets that an element belongs to; under the unique games conjecture, this approximation is best possible for any fixed f. This is the first algorithm for dynamic set cover with approximation ratio that exactly matches f (as opposed to almost f in prior work), as well as the first one with runtime independent of n, m (for any approximation factor of o(f3)). Prior to our work, the state-of-the-art algorithms for this problem were O(f2) update time algorithms of Gupta et al. [STOC'17] and Bhattacharya et al. [IPCO'17] with O(f3) approximation, and the recent algorithm of Bhattacharya et al. [FOCS'19] with O(f · log n/ε2) update time and (1 + ε) · f approximation, improving the O(f2 · log n/ε5) bound of Abboud et al. [STOC'19]. The key technical ingredient of our work is an algorithm for maintaining a maximal matching in a dynamic hypergraph of rank r - where each hyperedge has at most r vertices - that undergoes hyperedge insertions and deletions in O(r2) amortized update time; our algorithm is randomized, and the bound on the update time holds in expectation and with high probability. This result generalizes the maximal matching algorithm of Solomon [FOCS'16] with constant update time in ordinary graphs to hypergraphs, and is of independent merit; the previous state-of-the-art algorithms for set cover do not translate to (integral) matchings for hypergraphs, let alone a maximal one. Our quantitative result for the set cover problem is translated directly from this qualitative result for maximal matching using standard reductions. An important advantage of our approach over the previous ones for approximation (1 + ε) · f (by Abboud et al. [STOC'19] and Bhattacharya et al. [FOCS'19]) is that it is inherently local and can thus be distributed efficiently to achieve low amortized round and message complexities.

Original languageEnglish (US)
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772044
DOIs
StatePublished - Sep 1 2021
Event29th Annual European Symposium on Algorithms, ESA 2021 - Vitual, Lisbon, Portugal
Duration: Sep 6 2021Sep 8 2021

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume204
ISSN (Print)1868-8969

Conference

Conference29th Annual European Symposium on Algorithms, ESA 2021
Country/TerritoryPortugal
CityVitual, Lisbon
Period9/6/219/8/21

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Dynamic graph algorithms
  • Hypergraph
  • Matching
  • Maximal matching
  • Set cover

Fingerprint

Dive into the research topics of 'Fully dynamic set cover via hypergraph maximal matching: An optimal approximation through a local approach'. Together they form a unique fingerprint.

Cite this