# A variation of Set Cover

Suppose we have $$n$$ sets $$\{S_i\}_{i=1}^n$$, each containing exactly $$k$$ of the numbers from $$1,...,n$$. The union of all these sets will cover $$1,...,n$$. We know $$i \in S_i$$ for all $$i$$. We need to pick the minimum number of sets to cover $$1,...,n$$ such that if we pick $$S_t$$, then for all $$i \in S_t$$, we can not pick $$S_i$$ anymore.

What will be the minimum number of sets that we need to pick considering all possible permutations of the elements numbered $$1,...,n$$. We are not looking at a particular ordering of the numbers and sets (i.e. We want to know the expected number of sets needed to be picked to cover all the elements).

EDIT: We can also look at the problem from another viewpoint, not sure if this is any helpful way to look at it.

Consider those $$n$$ elements as just $$n$$ vertices of a $$k$$-regular graph and each $$S_i$$ is the neighborhood of $$i$$, i.e. $$N(i)$$. Now we want to pick the least number of neighborhoods so that the graph is completely partitioned.

• When you say "expected number", do you mean you don't want any particular algorithm for some choice of the $S_i$'s up to renumberings? You instead want an average $a_{n,k}$ or a minimum $m_{n,k}$ over all $S_i$'s and renumberings for $n$ and $k$ fixed? Apr 24, 2023 at 11:25
• But this is not always possible: what do we pick if $n=3$ and $S_i=\{i, i+1\}$ (enumeration of vertices is cyclic modulo 3)? Apr 24, 2023 at 11:36
• (and as stated, this is never possible: we take $S_t$, then for $i=t$ we get a contradiction.) Apr 24, 2023 at 11:38
• @ClaudeChaunier You are right. I was not looking for an algorithm for some choice of $S_i$'s. I wanted to know the average number of sets that can cover keeping $n,k$ fixed. Also, as pointed out by another comment, this is always not possible, but I am considering all such cases where such a situation exists. But again if there is an algorithm that can do this without depending on what $S_i$ looks like, i.e. for general input, then that will be awesome too. Apr 24, 2023 at 23:43
• @FedorPetrov I have added an edit to the question to show what kind of situation I am thinking about. You are right, there might not be a solution, but I am considering only the situations where this is possible and talking about average over all such situations. I don't know if thinking in terms of graph partitions makes it any easier, that was just to clarify what kind of problem I am looking at. Apr 24, 2023 at 23:49

The decision problem (i.e. whether $$m$$ sets suffice) is as hard as the 3-dimensional matching problem.
Given any 3-SAT instance, it is possible to construct a 3-uniform 3-regular hypergraph $$X$$ such that the 3-SAT instance has a solution iff the 3-uniform 3-regular hypegraph admits an exact cover.
Construct a bipartite graph $$G=(U,V,E)$$ based on the hypergraph $$X$$ as follows: $$U$$ is the vertex set of $$X$$, $$V$$ is the hyperedge set of $$X$$, and $$U \sim V$$ in $$G$$ iff $$U\in V$$ in $$X$$. Then $$G$$ is a 3-regular bipartite graph and has a perfect matching by Hall's theorem. Thus the vertex set of $$X$$ can be labelled by $$1,\dots,n$$ and the hyperedge set $$S_i$$ $$(i=1,\dots,n)$$ such that $$i \in S_i$$.
Let's call a covering $$S$$ of $$1,...,n$$ where $$S_t \in S$$ and $$i \in S_t$$ implies $$S_i \notin S$$ an A-cover. Obviously, all exact covers are A-covers, and A-covers with size $$n/3$$ are exact covers. Thus, deciding whether the minimum A-cover has size $$n/3$$ is as hard as deciding whether there is an exact cover, and the latter is NP-complete.