Improved Local Computation Algorithm for Set Cover via Sparsification

Christoph Grunau, Slobodan Mitrović, Ronitt Rubinfeld, Ali Vakilian

Abstract

In the era of massive datasets, computing global solutions to combinatorial problems is often computationally prohibitive. Local Computation Algorithms (LCAs) address this by determining the status of specific elements in a global solution using only a small number of local queries. This paper presents a novel LCA for the Set Cover problem that achieves a near-optimal $O(\log s)$ approximation ratio while significantly reducing query complexity through a technique known as sparsification.

Introduction

The Set Cover problem is a fundamental challenge in combinatorial optimization: given a collection of sets $\mathcal{S}$ over a universe of elements $\mathcal{E}$, the goal is to find the minimum number of sets whose union covers all elements. In many modern applications, such as large-scale social network analysis or logistics optimization, the input size is too vast to process globally.

Local Computation Algorithms provide a solution by acting as an "oracle." When queried about a specific set $S \in \mathcal{S}$, the LCA must decide whether $S$ belongs to a fixed set cover. This decision must be consistent across multiple queries and computed using only a local view of the data. The primary metric for evaluating LCAs is query complexity—the number of probes made to the input to determine the status of a single set.

The Challenge of Query Complexity

Historically, LCAs for Set Cover were developed by simulating distributed algorithms. However, this approach suffers from a significant bottleneck: if a distributed algorithm requires $R$ rounds, the corresponding local simulation typically exhibits a query complexity that grows exponentially with $R$.

For the Set Cover problem, standard reductions resulted in a query complexity of $(st)^{O(\log s \cdot \log t)}$, where $s$ is the maximum set size and $t$ is the maximum number of sets an element appears in (the maximum degree). As $s$ and $t$ grow, this complexity becomes increasingly inefficient. The research presented here aims to break this exponential dependency through a more refined local search strategy.

Methodology: The Sparsification Framework

The core innovation of this work is the application of sparsification to the Set Cover problem. Rather than exhaustively exploring the neighborhood of a set in the set-element bipartite graph, the algorithm "thins out" the search space to maintain efficiency.

1. Parallel Base Algorithm

The foundation is a parallel algorithm that adds sets to the cover based on the number of "free" (uncovered) elements they contain. A critical feature of this base algorithm is that it never revokes a decision once a set is added, which greatly simplifies the logic required for a consistent local simulation.

2. Size Estimation via Sampling

To avoid the high cost of counting every uncovered element in a set, the algorithm employs random sampling. By obtaining high-probability estimates of set sizes rather than exact counts, the algorithm significantly reduces the initial query load without sacrificing the quality of the final cover.

3. Recursive Splitting and Pruning

To prevent the "exponential explosion" of queries during the simulation of multiple rounds, the authors utilize a recursive splitting technique. The algorithm divides iterations into phases and sub-phases, pruning the neighborhood at each step. This involves removing sets that are unlikely to be selected and elements that are likely already covered, effectively reducing the branching factor of the local search tree.

4. Management of Bad Events

Sparsification introduces the risk of "bad events" where the random sampling or pruning might lead to a sub-optimal cover. The authors provide a rigorous probabilistic analysis to demonstrate that these events are sufficiently rare, ensuring that the algorithm maintains its approximation guarantees.

Key Results and Comparative Analysis

The proposed algorithm achieves a new state-of-the-art query complexity for Set Cover LCAs:

  • Query Complexity: $s^{O(\log s)} t^{O(\log s \cdot (\log \log s + \log \log t))}$.
  • Approximation Ratio: The algorithm maintains an expected approximation ratio of $O(\log s)$, which is the theoretical limit for Set Cover unless $P=NP$.

Compared to the previous baseline of $(st)^{O(\log s \cdot \log t)}$, this new approach offers a substantial reduction in the number of queries required, particularly in instances where the set sizes and element degrees are large.

Conclusion and Future Directions

This work demonstrates that sparsification, previously successful in problems like Maximal Independent Set (MIS), can be adapted for the bipartite structure of Set Cover. By replacing exhaustive neighborhood searches with estimation and recursive pruning, the authors have significantly advanced the efficiency of local computation.

Future research may focus on moving from an expected approximation guarantee to a deterministic one within the same query bounds. Additionally, the novel approximation analysis introduced in this paper may have broader applications for other packing and covering problems within the LCA model.

Summary updated

Abstract

We design a Local Computation Algorithm (LCA) for the set cover problem. Given a set system where each set has size at most $s$ and each element is contained in at most $t$ sets, the algorithm reports whether a given set is in some fixed set cover whose expected size is $O(\log{s})$ times the minimum fractional set cover value. Our algorithm requires $s^{O(\log{s})} t^{O(\log{s} \cdot (\log \log{s} + \log \log{t}))}$ queries. This result improves upon the application of the reduction of [Parnas and Ron, TCS'07] on the result of [Kuhn et al., SODA'06], which leads to a query complexity of $(st)^{O(\log{s} \cdot \log{t})}$. To obtain this result, we design a parallel set cover algorithm that admits an efficient simulation in the LCA model by using a sparsification technique introduced in [Ghaffari and Uitto, SODA'19] for the maximal independent set problem. The parallel algorithm adds a random subset of the sets to the solution in a style similar to the PRAM algorithm of [Berger et al., FOCS'89]. However, our algorithm differs in the way that it never revokes its decisions, which results in a fewer number of adaptive rounds. This requires a novel approximation analysis which might be of independent interest.
BibTeX
@inproceedings{grunau2020improved,
  author = {Christoph Grunau and Slobodan Mitrović and Ronitt Rubinfeld and Ali Vakilian},
  title = {{Improved Local Computation Algorithm for Set Cover via Sparsification}},
  booktitle = {SODA},
  year = {2020},
  url = {https://openreview.net/forum?id=khk58re9BJ},
}
Figure