Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time

Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger

TL;DR

This paper presents the first deterministic algorithm that can maintain an approximate minimum vertex cover and maximum fractional matching in a dynamic graph with an amortized update time of O(1). This is a significant theoretical breakthrough, removing the need for an oblivious adversary that was previously required for such fast dynamic algorithms.

What Problem Does This Paper Address?

Maintaining graph properties like maximum matching or minimum vertex cover in graphs that change over time (edges are inserted or deleted) is a fundamental problem in computer science. The "dynamic matching problem" and its dual, the "approximate vertex cover problem," have been studied extensively. While randomized algorithms have achieved O(1) amortized update times, they typically rely on an "oblivious adversary," meaning the sequence of graph changes cannot depend on the algorithm's past outputs. This is a strong assumption that doesn't hold in many real-world scenarios. The challenge has been to achieve this O(1) amortized update time deterministically, without the oblivious adversary assumption. Previous deterministic algorithms offered much slower update times (e.g., O(log n / ε²)).

Methods

The core of the algorithm is a sophisticated hierarchical partitioning of vertices. This approach, building on prior work, divides nodes into multiple levels. The algorithm maintains fractional weights on hyper-edges and ensures certain invariant conditions related to these weights and node levels.

The key innovation lies in how they handle violations of these invariants. Instead of simply fixing the immediate violation, their "fixing procedure" often enforces a stronger condition than strictly necessary. This "slack" allows for a charging argument: if a node's weight increases again, it implies that other significant events (like edge insertions) must have occurred. This allows them to bypass the O(log n) dependency on the number of levels and achieve O(1) amortized update time. The trade-off for this speedup is a slightly weaker approximation ratio (O(1) instead of O(2+ε)). The algorithm also generalizes to hypergraphs, where it achieves an O(f³) approximation with O(f²) amortized update time, where 'f' is the maximum size of a hyperedge.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Deterministic O(1) Amortized Update Time: This is the headline result. Achieving constant time updates deterministically for dynamic graph problems is rare and theoretically significant, especially for problems where lower bounds suggest non-constant times might be necessary in other models.
  • "Slack" for Amortization: The technique of enforcing stronger invariants than strictly needed to create "slack" is a clever way to enable amortized analysis and bypass logarithmic factors.
  • Approximation vs. Update Time Trade-off: The paper explicitly highlights that the O(1) update time comes at the cost of a slightly weaker O(1) approximation ratio, demonstrating a common theme in algorithm design.
  • Generalization to Hypergraphs: The algorithm's ability to extend to hypergraphs, a more general structure, adds to its impact.

Key Results

  • A deterministic fully dynamic algorithm for maintaining an O(1)-approximate minimum vertex cover and maximum fractional matching with an O(1) amortized update time.
  • This algorithm works even against an adaptive adversary.
  • The algorithm generalizes to hypergraphs, providing an O(f³)-approximate algorithm for vertex cover and fractional matching with an O(f²) amortized update time, where 'f' is the maximum hyperedge size.

Limitations and Future Work

  • Approximation Ratio: While O(1) is constant, it's not as tight as the O(2+ε) achieved by some randomized algorithms. The paper notes it would be interesting to see if this approximation ratio can be improved without sacrificing the O(1) update time.
  • Hypergraph Approximation: The O(f³) approximation for hypergraphs might also be improvable. The paper mentions independent work by Gupta et al. achieving the same approximation ratio with the same update time.
  • Practicality: The theoretical nature of the O(1) amortized time suggests that constant factors might be large, and practical performance would need empirical validation.

The paper opens avenues for exploring similar trade-offs between approximation quality and update time in other dynamic graph problems.

Summary updated

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(\log n/\epsilon^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.
BibTeX
@inproceedings{bhattacharya2017deterministic,
  author = {Sayan Bhattacharya and Deeparnab Chakrabarty and Monika Henzinger},
  title = {{Deterministic Fully Dynamic Approximate Vertex Cover and Fractional Matching in O(1) Amortized Update Time}},
  booktitle = {IPCO},
  year = {2017},
  url = {https://openreview.net/forum?id=noREnEwu9qg},
}
Figure