0
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – Claude Chaunier
    Commented Apr 24, 2023 at 11:25
  • $\begingroup$ 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)? $\endgroup$
    – Fedor Petrov
    Commented Apr 24, 2023 at 11:36
  • $\begingroup$ (and as stated, this is never possible: we take $S_t$, then for $i=t$ we get a contradiction.) $\endgroup$
    – Fedor Petrov
    Commented Apr 24, 2023 at 11:38
  • $\begingroup$ @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. $\endgroup$
    – Jackson
    Commented Apr 24, 2023 at 23:43
  • $\begingroup$ @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. $\endgroup$
    – Jackson
    Commented Apr 24, 2023 at 23:49

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the great answer! So an approximation algorithm for the 3-dim matching problem can give an approximation to the optimal number of required sets (or least number of neighborhoods based on my recent edit to the question) in my problem too, right? $\endgroup$
    – Jackson
    Commented Apr 25, 2023 at 1:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .