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:
- 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.
- 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.
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