Optimal distributed covering algorithms

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, Gregory Schwartzman

Abstract

This paper introduces a time-optimal, deterministic distributed algorithm for the Minimum Weight Hypergraph Vertex Cover (MWHVC) problem. Operating within the CONGEST model, the algorithm achieves an $(f + \epsilon)$-approximation in $O(\log \Delta / \log \log \Delta)$ rounds for constant rank $f$ and error $\epsilon$. This marks the first algorithm for MWHVC with a runtime entirely independent of network size ($n$) and vertex weights ($W$), matching theoretical lower bounds.

Introduction

The Minimum Weight Hypergraph Vertex Cover (MWHVC) problem is a fundamental optimization task where the goal is to find a set of vertices with minimum total weight that covers every hyperedge in a hypergraph. In a hypergraph of rank $f$, each hyperedge connects at most $f$ vertices. This problem is mathematically equivalent to the Minimum Weight Set Cover problem and has significant applications in distributed resource allocation.

The authors investigate this problem in the CONGEST model, a standard distributed computing framework where nodes communicate in synchronous rounds using messages limited to $O(\log V)$ bits. Prior distributed solutions often suffered from runtimes dependent on the total number of vertices ($n$) or the dynamic range of vertex weights ($W$). The objective of this work is to develop a strictly "local" algorithm whose complexity depends solely on the maximum degree $\Delta$.

Methodology: Primal-Dual and Leveling

The proposed algorithm utilizes a deterministic Primal-Dual schema. It maintains a fractional dual solution, which can be interpreted as "bids" placed by hyperedges on their incident vertices. To overcome the bandwidth constraints of the CONGEST model, the authors introduce two key mechanisms:

  1. Leveling Mechanism: Each vertex monitors its "tightness"—the proximity of its accumulated bids to its weight—using discrete levels. These levels represent the logarithm of the vertex's uncovered weight.
  2. Exponential Bidding: Hyperedges propose bids that increase exponentially (scaled by a factor $\alpha$). If all vertices in a hyperedge can accommodate the increased bid without exceeding their capacity, they signal a "raise." If a vertex becomes "tight," it joins the vertex cover and notifies its neighbors.

This approach ensures that dual variables grow rapidly, minimizing communication rounds while strictly adhering to packing constraints.

Key Results and Performance

The primary contribution is an $(f + \epsilon)$-approximation for MWHVC in $O(\log \Delta / \log \log \Delta)$ rounds, assuming $f$ and $\epsilon$ are constants. This complexity matches the known lower bounds for constant approximation ratios, placing the algorithm among the few provably optimal distributed algorithms.

Comparison of distributed algorithms for hypergraph vertex cover and related problems.

Beyond the main result, the algorithm offers several improvements over previous benchmarks:

  • Exact $f$-Approximation: By adjusting parameters, it achieves a strict $f$-approximation in $O(f \log n)$ rounds, improving upon the $O(f \log^2 n)$ requirement of previous classic results.
  • Weighted Vertex Cover: For standard graphs ($f=2$), the algorithm provides a deterministic $O(\log n)$ runtime, matching the performance of the best-known randomized algorithms.
  • ILP Generalization: The authors demonstrate a reduction showing that any general covering Integer Linear Program (ILP) can be solved using this MWHVC framework, yielding an $(f \lceil \log_2(M) \rceil + 1 + \epsilon)$-approximate solution in optimal time.

Conclusion

By decoupling runtime from network size and vertex weights, this work provides a robust and theoretically optimal framework for distributed covering problems. The use of primal-dual techniques combined with exponential bidding establishes a new standard for efficiency in the CONGEST model, with broad implications for solving general linear optimization problems in a decentralized manner.

Summary updated

Abstract

We present a time-optimal deterministic distributed algorithm for approximating a minimum weight vertex cover in hypergraphs of rank f. This problem is equivalent to the Minimum Weight Set Cover problem in which the frequency of every element is bounded by f. The approximation factor of our algorithm is \((f+\varepsilon )\). Let \(\varDelta \) denote the maximum degree in the hypergraph. Our algorithm runs in the congest model and requires \(O(\log {\varDelta } / \log \log \varDelta )\) rounds, for constants \(\varepsilon \in (0,1]\) and \(f\in {\mathbb {N}}^+\). This is the first distributed algorithm for this problem whose running time does not depend on the vertex weights nor the number of vertices. Thus adding another member to the exclusive family of provably optimal distributed algorithms. For constant values of f and \(\varepsilon \), our algorithm improves over the \((f+\varepsilon )\)-approximation algorithm of Kuhn et al. (SODA, 2006)whose running time is \(O(\log \varDelta + \log W)\), where W is the ratio between the largest and smallest vertex weights in the graph. Our algorithm also achieves an f-approximation for the problem in \(O(f\log n)\) rounds, improving over the classical result of Khuller et al. (J Algorithms, 1994) that achieves a running time of \(O(f\log ^2 n)\). Finally, for weighted vertex cover (\(f=2\)) our algorithm achieves a deterministic running time of \(O(\log n)\), matching the randomized previously best result of Koufogiannakis and Young (Distrib Comput, 2011). We also show that integer covering-programs can be reduced to the Minimum Weight Set Cover problem in the distributed setting. This allows us to achieve an \((f\lceil \log _2(M)+1 \rceil +\varepsilon )\)-approximate integral solution in
BibTeX
@inproceedings{benbasat2019optimal,
  author = {Ran Ben-Basat and Guy Even and Ken-ichi Kawarabayashi and Gregory Schwartzman},
  title = {{Optimal distributed covering algorithms}},
  booktitle = {DISC},
  year = {2019},
  doi = {10.4230/lipics.disc.2019.5},
}
Figure