PaperlayerView exact revision on arXiv

Source-linked AI summary

Settling the Pass Complexity of Streaming Set Cover

Sepehr Assadi, Janani Sundaresan

arXiv:2610.01007v1cs.DS

TL;DR

Streaming set cover seeks non-streaming-quality approximations using sublinear space, but progress on low-space algorithms has stalled while even a two-pass O(m)-space O(log n)-approximation remains plausible. This paper uses a pointer-chasing reduction to prove a nearly optimal space-pass-approximation tradeoff, including an eOmega(m n^(1/p)) space lower bound for log n and polylog(n) approximations.

  • Problem

    Low-space streaming algorithms aim to match non-streaming set cover's log n or polylog(n) approximation, but progress has stalled and known lower bounds still leave an O(m)-space, two-pass O(log n)-approximation plausible.

    Source: §1 · pp. 3–4

  • Method

    A direct reduction from pointer chasing, analyzed using elementary properties of random sets, establishes the set cover lower bound.

    Source: §1.2 · p. 6

  • Results

    Any log n or polylog(n)-approximation algorithm requires eOmega(m n^(1/p)) space in p passes, settling the conjecture of [HIMV16].

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    The result establishes a nearly optimal three-way space-pass-approximation tradeoff for streaming set cover.

    Source: §1.1 · p. 4

    The proof's parameter choice requires p ≪ m and p·α = o((n/log m)^(1/(p+1))).

    Source: §3.2 · p. 14

Abstract

from arXiv · show

In the streaming set cover problem, $m$ sets from a universe of size $n$ are arriving one by one in a stream, and the algorithm is allowed to process the stream using one or a few passes and a space of $o(mn)$, which is sublinear in the input size. The goal is to determine the minimal (or approximately minimal) number of sets that cover the universe at the end of the last pass. This problem has been studied extensively over the years with rapid progress that led to several $O(\log{n})$-approximation algorithms in $\tilde{O}(mn^{1/p})$ space and $O(p)$ passes. However, progress on this front has largely stagnated over the past decade, despite the absence of any lower bounds that rule out even an $O(\log{n})$-approximation in $O(m)$ space and just two passes. We provide a simple explanation for this lack of progress by establishing an optimal three-way space-pass-approximation tradeoff for this problem: any $\alpha$-approximation algorithm for streaming set cover requires $$ \widetilde{\Omega}\Big(\frac{m}{\alpha} \cdot \big(\frac{n}{\alpha}\big)^{1/p}\Big) $$ space in $p$ passes whenever $\alpha \ll n^{1/(p+1)}$. In light of prior work, this result is optimal up to constant factors in $p$ and logarithmic factors in $n,m$ for any $\alpha\geq p$. Our bound is optimal with respect to the range of $\alpha$ also, and fully settles the complexity of this fundamental problem in the streaming model. The proof of this result is (surprisingly) simple and non-technical and relies on a randomized reduction from a variant of the standard pointer chasing problem in communication complexity, using elementary properties of random sets.

1 Introduction

Streaming set cover seeks small-space, few-pass approximations, but prior work left open whether even an O(log n)-approximation could use O(m) space in two passes. The paper gives a nearly optimal space–pass–approximation tradeoff and a randomized pointer-chasing reduction analyzed using random sets.

1 Introduction

  • Set cover asks for the smallest collection of sets whose union covers an n-element universe; streaming algorithms process the m sets in one or a few passes using o(mn) space.Storing all sets explicitly takes Θ(mn) space.Source: §1 · p. 3
  • Prior algorithms reached O(log n)-approximations with sublinear space, yet known lower bounds still left an O(m)-space, two-pass O(log n)-approximation plausible.The literature had made little algorithmic progress on this question for nearly a decade.Source: §1 · pp. 3–4

1.1 Our Contributions

  • Theorem 1 establishes a nearly optimal three-way space–pass–approximation tradeoff, settling the [HIMV16] conjecture for logarithmic and polylogarithmic approximations.For log n or polylog(n) approximations, the stated lower bound is eΩ(mn^(1/p)) space in p passes.Source: §1.1 · p. 4
  • The bound is nearly optimal up to constant factors in p, and its parameter range is necessary: below α=p, gives a stronger bound, while at α≥n^(1/(p+1)), [CW16] gives eO(n) space.For p=Ω(log n), [SG09, CW16] also give an O(log n)-approximation using eO(n) space and O(log n) passes.Source: §1.1 · p. 4
  • The theorem extends [AKL16]’s single-pass Ω(mn/α^2) space lower bound to multiple passes, matching its tradeoff when p=1.It also strengthens [CW16]’s multi-pass result to require Ω(m) space for (n/log n)^(1/(p+1))-approximation, with a (log n)^(1/(p+1)) loss in approximation ratio.Source: §1.1 · p. 4

1.2 Our Techniques

  • The proof uses a direct randomized reduction from pointer chasing and elementary random-set properties, rather than [CW16]’s many separate hard instances and algebraic edifices.The construction uses mildly correlated, approximately n/log n-sized sets that point to one another; useful pointer information remains negligible until the hidden universe is revealed.Source: §1.2 · pp. 5–6

2 Preliminaries

The preliminaries define multi-party pointer chasing and state a communication lower bound for solving it. They also recall Chernoff bounds, including an upper-tail extension to negatively correlated variables.

2 Preliminaries

  • The upper-tail Chernoff bound also applies when the variables are negatively correlated.The section introduces the standard Chernoff bound and its extension to negatively correlated variables.Source: §2 · p. 7
  • Pointer chasing PCp,a,b has p+1 players; P1 holds a balanced Boolean function f1:[a]×[b]→{0,1}, while each other player holds fi:[a]×[b]→[a]×[b]; they speak in order over p rounds.Source: §2 · p. 7
  • A randomized protocol solving PCp,a,b with probability at least 3/5 requires a lower bound on total message length.The supplied proposition states the bound but does not include its value.Source: §2 · p. 7
  • Figure 1 illustrates pointer chasing with p = 3, a = 3, and b = 4, ending with answer 0.Grids represent functions, green highlights special pointers, and red dashed arrows show pointer movement.Source: Figure 1 · p. 8

3 Proof of the Main Result

The proof reduces pointer chasing to streaming set cover by encoding the pointer-chasing answer in an instance’s cover size, then uses an approximation algorithm to form a protocol and applies pointer-chasing impossibility to lower-bound space.

3.1 Protocol for Pointer Chasing

  • Public randomness creates U-common sets, while players use their own pointers to construct S-private sets; together, they produce exactly m sets.The sets are collectively used as the set-cover instance supplied to the approximation algorithm.Source: §3.1 · p. 8, Creation of Set Cover Instance · pp. 10–11
  • If pointer chasing returns 1, at most p+1 sets cover the universe; otherwise, with high probability, no α(p+1) sets cover it.This gap is the basis for distinguishing the two pointer-chasing outcomes through a set-cover approximation.Source: Creation of Set Cover Instance · pp. 11–12
  • The players decode pointer chasing by outputting 1 when the algorithm estimates a cover size at most α(p+1), and 0 otherwise.The protocol runs the p-pass algorithm through p+1 players using p rounds and total communication (p+1)·p·s.Source: Creation of Set Cover Instance · p. 13
  • If A succeeds with probability at least 2/3, protocol π solves PCp,a,b with probability at least 3/5 for large m, n and α ≥ 1.When pointer chasing outputs 1, the optimal cover has size at most p + 1; when it outputs 0, the cover exceeds α(p + 1) with high probability.Source: Creation of Set Cover Instance · p. 14

3.2 Finishing the Proof of Theorem 1

  • Choosing the parameters as specified in Eq. (1), the pointer-chasing impossibility result yields a space lower bound for A, completing the proof of Theorem 1.The parameter choice is feasible under p ≪ m and p · α = o((n / log m)^(1/(p+1))).Source: §3.2 · p. 14

A An Algorithm for Streaming Set Cover Estimation

This appendix presents a streaming algorithm matching the paper's tradeoff up to polylogarithmic factors and constant factors in p. It combines primitives from prior work to find an approximate set cover in O(p) passes.

A An Algorithm for Streaming Set Cover Estimation

  • A modification of [AKL16, HIMV16] gives an algorithm matching Theorem 1's tradeoff up to polylogarithmic factors and constant factors in p.The cited prior work concerns set cover estimation in one pass and approximate set cover in multiple passes.Source: A An Algorithm for Streaming Set Cover… · p. 19
  • For any n, m, p, and α ≥ 1, a streaming algorithm finds an α-approximate set cover in O(p) passes with high probability.The supplied proposition omits the space expression.Source: A An Algorithm for Streaming Set Cover… · p. 19
  • The appendix proves the needed primitives from [AKL16] and [HIMV16] for completeness.For K ⊆ U, O(K) denotes an optimal family cover of K, and opt(K) its size.Source: A An Algorithm for Streaming Set Cover… · p. 19

A.1 Estimating Set Cover Size in One Pass

Randomly sampled smaller universes can test estimates of the optimal set-cover size. The proof uses several such samples to show that a too-small sampled optimum would contradict optimality on the original universe.

A.1 Estimating Set Cover Size in One Pass

  • Sampling k = 4β smaller universes conditioned on opt(U′) < t leads to a contradiction if their optimal covers together cost less than opt(U).The argument bounds the union of the covers by (opt(U)/8β + 1)·4β = opt(U)/2 + 4β < opt(U).Source: §A.1 · pp. 20–21
  • A union bound yields sampled universes that collectively contain every element of U, enabling the contradiction from the cost of their optimal covers.The proof samples k = 4β universes and uses the resulting covers to cover U.Source: §A.1 · pp. 20–21
  • A sampled smaller universe supports testing a guess for opt(U): accept the guess when opt(U′) is no larger than it.The naive implementation uses eO(mn/β) space; the text says multiple passes can improve this using [HIMV16].Source: §A.1 · p. 21

A.2 Covering Original Universe with Smaller Samples

Independent element sampling produces a smaller universe whose covers constrain how many original elements can remain uncovered. The proof obtains the guarantee by ruling out, with a union bound, any small family that covers the sample but leaves too many original elements uncovered.

A.2 Covering Original Universe with Smaller Samples

  • With probability at least 1 − 1/n^2, any set family covering U′ leaves at most n^(1−γ) elements of U uncovered.The guarantee is for U with at most n elements and the sampling probability specified in the lemma.Source: §A.2 · p. 21
  • The sampling probability is r = 100·opt(U)·log m·log n·n^(γ−1).Here γ is in (0, 1), and the lemma’s failure probability is at most 1/n^2.Source: §A.2 · p. 21
  • The proof rules out families of at most opt(U) sets that leave n^(1−γ) or more elements uncovered yet still cover U′.It bounds the number of candidate families by m^(2ℓ) and applies a union bound.Source: §A.2 · p. 21

A.3 Estimating Set Cover Size

The algorithm estimates set-cover size by testing guesses using sampled universes, pruning covered elements over multiple iterations, and checking whether a guess is too small. Its guarantees combine acceptance of sufficiently large guesses with rejection of sufficiently small ones.

A.3 Estimating Set Cover Size

  • The algorithm tests whether opt(U) ≥ k or opt(U) = o(k/α) using an approximate cover of a sampled universe across multiple passes.It uses Lemma A.2 to estimate cover size and Lemma A.4 to find an approximate sampled-universe cover.Source: §A.3 · p. 21
  • With high probability, the algorithm accepts k ≥ opt(U) and rejects k ≤ opt(U)/(32α); O(log m) guesses yield an estimate.The proof runs O(log n) parallel checks per guess and reparameterizes α to obtain an α-approximation without changing space asymptotically.Source: §A.3 · pp. 22, 25
  • When the algorithm accepts, the pruning step adds at most β·k·p sets that cover U_pr.In each of p iterations, at most β·k sets are added during pruning.Source: §A.3 · pp. 22–23
  • With probability at least 1 − 1/n, after iteration i the remaining U_left has size at most (n_samp)^(1−i/p).The induction uses Lemma A.4 to shrink the remainder at each iteration.Source: §A.3 · p. 23
  • When ALG accepts, opt(U_samp \ U_pr) ≤ k·p with probability at least 1 − 1/n.The proof argues that the selected sets cover the residual sampled universe after p iterations.Source: §A.3 · p. 23
  • If k < opt(U)/(32α), ALG rejects with probability at least 1/2.The proof combines the sampled-universe estimate with the bound on the residual cover size.Source: §A.3 · pp. 23–24
  • Each iteration uses two passes, and the space analysis bounds the expected sampled set size by 100·k·log m·log n·(n_samp)^(1/p).The expectation follows from the bound on U_left at the start of iteration i.Source: §A.3 · p. 24
  • The sampled universe has size at most 8·ln n·n·p/α with high probability.Each element is sampled with probability 4·ln n·p/α, giving expected sample size 4·n·ln n·p/α.Source: §A.3 · p. 25
Loading 2610.01007v1…