# Is there a distributed streaming algorithm to verify set cover?

I have $$k$$ sets of similar sizes, that cover a universe $$U$$.

e.g. for $$k=3$$ and $$U = \{1, 2, 3, 4, 5, 6\}$$:

$$S_0 = \{1, 2, 4\}$$

$$S_1 = \{2, 3, 4\}$$

$$S_2 = \{4, 5, 6\}$$

I have another larger set $$C$$ guaranteed to be subset of $$U$$.

$$C \subseteq \bigcup\limits_{i=0}^{k} s_{i}$$.

e.g. $$C = \{1, 2, 3, 4, 5\}$$

I want to be able to verify whether $$C$$ and $$U$$ are equal or not.

Is there a distributed streaming algorithm that has a minimal space complexity with an acceptable false positive rate?

• Sets $$S_i$$ are distributed on independent nodes, they need to be processed independently.
• $$C$$ is local.

An ideal solution would process the subsets $$S_0,S_1, .. S_k$$ in a single pass and create a sketch or a summary structure which then could be combined to verify against $$C$$. $$C$$ can be processed in multiple passes.

My thoughts towards a solution:

I thought of using an $$n$$-bit hashing algorithm. After hashing every element I could mark them on a bitset of size $$2^n$$. OR'ing these bitsets would give me the bitset of their union. Therefore I can calculate these bitsets once per $$S_i$$, collect these bitsets, OR them to compare against the bitset of $$C$$.

I'm not sure if there's a better solution than this (or even if this is a good solution or not). I can't really tell what would the false positive rate be, but I can tell it will be smaller as $$n$$ grows (at the exponential expense of bitset space).

Note: I had asked a similar question earlier: Fingerprint functions for set equality checks?. I realized later on, the actual problem I'm trying to solve is the special case of that problem. Here the larger set $$C$$ is guaranteed to be a subset of the union of all smaller sets $$S_0, S_1, .. S_k$$.

• This is not a streaming algorithm, but uses a gossip model, so it may be useful: arxiv.org/abs/1904.10706 . The main idea is to rephrase the problem as an LP-type problem, and use a distributed version of Clarksons algorithm (which is a Las Vegas algorithm). Jan 30, 2022 at 12:37