<p><strong>Lemma.</strong> <em>The problem is NP-hard.</em></p>

<p><em>Proof sketch.</em>  We disregard the constraints $|F_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,k)$ obtained by taking the union of $n$ independent copies of $(F,U,k)$ (where the $i$th copy of $F$ uses the $i$th copy of $U$ as its base set) is equivalent, and satisfies the constraint (it has $|F'_i| \le n \ll n^2 = |U'|$).</p>

<p>We give a reduction from 3-SAT.  For presentation, in the first stage of the reduction, we disregard the constraints $e_i \in F_i$ in the posted problem.  In the second stage we describe how to meet those constraints while maintaining correctness of the reduction.</p>

<p><strong>First stage.</strong> Fix any 3-SAT formula $\phi$.  Assume WLOG that each clause has exactly three literals (each using a different variable). Produce the following instance $(F,U,k)$ of the posted problem, with $k=3$.</p>

<p>Let $n$ be the number of variables in $\phi$.
There are $3n+1$ elements in $U$: one element $t$ (for "true"), and, for each variable $x_i$ in $\phi$, three elements $x_i$, $\overline x_i$, and $f_i$ (for "false").</p>

<p>For each element in $U$ there is a singleton set containing just that element in $F$.  Any solution $C$ therefore includes each of these sets, which contribute their total size $3n+1$ to the cost of $C$.</p>

<p>In addition, for each variable $x_i$ in $\phi$ there is a "variable" set $\{x_i, \overline x_i, f_i, t\}$ in $F$.  For each clause in $\phi$ there is a "clause" set in $F$ consisting of the literals in the clause, and $t$.  For example, the clause $x_1\wedge \overline x_2 \wedge x_3$ yields the set $\{x_1, \overline x_2, x_3, t\}$ in $F$.</p>

<p><strong>Claim 1.</strong> <em>The reduction is correct: $\phi$ is satisfiable iff some solution $C$ has cost $\sum_j |C_j| = 5n+1$.</em></p>

<p><em>(only if)</em> Suppose $\phi$ is satisfiable. Construct a solution $C$ consisting of the $3n+1$ singleton sets, plus, for each variable $x_i$, the pair consisting of the true literal and $t$.  (E.g., $\{\overline x_i, t\}$ if $x_i$ is false.)  The cost of $C$ is then $5n+1$.  </p>

<p>Each variable set $\{x_i, \overline x_i, f_i, t\}$ is the union of three sets: the pair consisting of the true literal and $t$, plus two singleton sets, one for each of the other two elements.  (E.g., $\{\overline x_i, t\}, \{x_i\}, \{f_i\}$.)</p>

<p>Each clause set (e.g. $\{x_1, \overline x_2, x_3, t\}$) is the union of three sets: a pair consisting of $t$ and a true literal, plus two singleton sets, one for each of the other two literals.  (E.g., $\{x_1, t\}, \{\overline x_2\}, \{x_3\}$.)</p>

<p><em>(if)</em> Suppose there is a solution $C$ of size $5n+1$.  The solution must contain the $3n+1$ singleton sets, plus other sets of total size $2n$.</p>

<p>Consider first the $n$ "variable" sets, each of the form $\{x_i, \overline x_i, f_i, t\}$.  The set is the disjoint union of at most three sets in $C$.  Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in $C$ achieves this without increasing the cost).  Denote the pair $P_i$.  The pairs $P_i$ and $P_j$ for different variables $x_i$ and $x_j$ are distinct, because $P_i$ contains $x_i$, $\overline x_i$, or $f_i$ but $P_j$ does not.  Hence, the sum of the sizes of these pairs is $2n$.  So these pairs are the only non-singleton sets in the solution.  </p>

<p>Next consider the "clause" sets, e.g, $\{x_i, \overline x_j, x_k, t\}$.  Each such set must be the union of at most three sets in $C$, that is, up to two singleton sets and at least one pair $P_i$, $P_j$, or $P_k$.  By inspection of the pairs and the clause set, it must be the union of two singletons and one pair, and that pair must be of the form $\{x_i, t\}$ or $\{\overline x_j, t\}$ (a literal and $t$).</p>

<p>Hence, the following assignment satisfies $\phi$: assign true to each variable $x_i$ such that $P_i=\{x_i, t\}$, assign false to each variable $x_i$ such that $P_i=\{\overline x_i, t\}$, and assign the remaining variables arbitrarily.</p>

<p><strong>Stage 2.</strong> The instance $(F,U,k=3)$ produced above does not satisfy the  constraint $e_i \in F_i$ stated in the problem description.  Fix that shortcoming as follows.  Order the sets $F_i$ and elements $e_i$ in $U$ so that each singleton set corresponds to its element $e_i$.  Let $m$ be the number of clauses in $\phi$, so $|F|=1+4n+m$ and $|U|=1+3n$.</p>

<p>Let $(F', U', k'=4)$ denote the instance obtained as follows. Let $A$ be a set of $2n+2m$ new artificial elements, two for each non-singleton set in $F$. Let $U'=U\cup A$. Let $F'$ contain the singleton sets from $F$, plus, for each non-singleton set $F_i$ in $F$, two sets $F_i\cup \{a_i, a_i'\}$ and $\{a_i,a_i'\}$, where $a_i$ and $a_i'$ are two elements in $A$ chosen uniquely for $F_i$.  Now $|F'|=|U'|=1+5n+2m$ and (with the proper ordering of $F'$ and $U'$) the constraint $e'_i\in F'_i$ is met for each set $F'_i$.</p>

<p>To finish, note that $(F',U',k'=4)$ has a solution of cost $|A|+5n+1$ iff the original instance $(F, U, k=3)$ has a solution of cost $5n+1$.</p>

<p><em>(if)</em>  Given any solution $C$ of cost $5n+1$ for $(F,U,k=3)$, adding the $n+m$ sets $\{a_i, a'_i\}$ (one for each non-singleton $F_i$, so these partition $A$) to $C$ gives a solution to $(F', U', k'=4)$ of cost $|A|+cost(C)=|A|+5n+1$.</p>

<p><em>(only if)</em> Consider any solution $C'$ for $(F', U',k=4)$ of cost $|A|+5n+1$.  Consider any pair of non-singleton sets $F_i\cup\{a_i, a_i'\}$ and $\{a_i, a_i'\}$ in $F'$.  Each is the disjoint union of at most 4 sets in $C'$. By a local-exchange argument, one of these sets is $\{a_i, a_i'\}$ and the rest don't contain $a_i$ or $a_i'$ --- otherwise this property can be achieved by a local modification to the sets, without increasing the cost... (lack of detail here is why I'm calling this a proof <em>sketch</em>). So removing the $\{a_i, a_i'\}$ sets from $C'$ gives a solution $C$ for $(F,U,k=3)$ of cost $5n+1$.  $\diamond$</p>

CC BY-SA 3.0
2017-05-21T08:53:50.183Z
2017-05-21T09:04:44.573Z
2017-05-21T09:04:44.573Z
Neal Young
<p>Consider a collection of sets $F=\{F_1,F_2,\dotsc,F_n\}$ over a base set $U=\{e_1,e_2,\dotsc,e_n\}$ where $|F_i|$ $\ll$ $n$ and $e_i \in F_i$, and let $k$ be a positive integer.</p>

<p>The goal is to find another collection of sets $C=\{C_1,C_2,\dotsc,C_m\}$ over $U$ such that each $F_i$ can be written as a union of at most $k$ $(k&lt;&lt;|C|)$ <strong>mutually disjoint</strong> sets in $C$ and also we want $\sum_1^m |C_j|$ to be minimal (i.e., the aggregate number of elements in all sets of $C$ should be as small as possible) .</p>

<p>Note that $F$ has the same size with $U$, but the size of $C$ is uncertain.</p>

<p>Can anyone tell whether the above problem is NP-hard? (set covering？packing？perfect covering）</p>

<p>Thanks for your time.</p>

CC BY-SA 3.0
2012-08-25T15:02:31.227Z
I don't understand what the "problem" is. What is it that you want to answer?
Ankur
CC BY-SA 3.0
2012-08-25T15:52:10.740Z
I have re formatted the problem. Thanks. @Ankur
Rhein
CC BY-SA 3.0
2012-08-26T05:10:19.723Z
Is $k$ given as a part of the problem definition or do you want or is it enough to find $C$ such that the property holds for some $k$? If it is the latter, then take $C=\{ \{e_i\}, i=1...n\}$ and $k = max_i |F_i|$.
Ankur
CC BY-SA 3.0
2012-08-26T05:13:51.033Z
I don't know if this is indeed a known version of Set Cover, but I thought I would suggest a keyword to help you in finding the answer - a cover by mutually disjoint sets is called a "perfect cover".
Ankur
CC BY-SA 3.0
2012-08-26T14:09:31.810Z
Why isn't this problem trivial by setting C={U}?
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-26T16:06:38.307Z
Note that one constraint is "no more than k". You just remind me of another constraint since C = {F} is trivial under this statement. I'll add another constraint. Thanks.
Rhein
CC BY-SA 3.0
2012-08-26T16:30:53.257Z
(1) Thank you for correcting the question.  (2) What does “|F|<<n” precisely mean?  I think that you meant to write |F_i| instead of |F|, but even if I assume this, I do not know what exactly “|F_i|<<n” means.  (3) I may be picky, but why did you label [your edit](http://cstheory.stackexchange.com/posts/12403/revisions) (revision 10) as “improved formatting”?  It is not the matter of formatting.  It is a correction to the question.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-26T16:40:24.727Z
|F_i|<<n,means each set in F has a size much smaller than n.
Yes, it's a correction, sorry for the confusing label.
Rhein
CC BY-SA 3.0
2012-08-26T16:45:54.000Z
Well, my question was: what is the precise meaning of “much smaller” in this context?
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-26T16:52:44.617Z
Beside the precise meaning of “much smaller,” I still have trouble understanding the problem.  As is stated in revision 11, it seems to me that the optimal solution is always C=∅ or C={∅}.  If we add a constraint that C contains at least one nonempty set as an element, then C={{e}} for some element e∈U will be the optimal.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-27T14:10:51.930Z
1.Just in case that someone may make the assumption that F_i = U. So "|F_i|<<n" is given explicitly. 2.Neither C=∅ nor C={∅} works since in these two cases F_i can't be calculated as a union of sets from C.  Does the statement of problem bring ambiguity? What I want to express is that each F_i can be a union of no more than K mutually disjoint sets from C.
Rhein
CC BY-SA 3.0
2012-08-27T14:44:28.047Z
Please read your own question carefully.  You have never said that C must be chosen so that F_i can be written as a union of sets from C.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-27T14:51:11.967Z
Now I see what you and I interpreted differently.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-27T16:41:25.847Z
I had been misinterpreting “no more than k sets.”  My apologies for that.  But I hope that my edit made the question easier to understand anyway!
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-28T06:09:54.663Z
It is trivial if $k\ge n$.
Martin B.
CC BY-SA 3.0
2012-08-28T14:26:42.590Z
$k<<n$. And actually in real application, $k$ is a variant rather than a constant. Each $F_i$ has its own value for $k$. @MartinB.
Rhein
CC BY-SA 3.0
2012-09-02T11:11:51.187Z
Can I view the NORMAL SET BASIS problem as a subproblem of the original one?
Rhein
CC BY-SA 3.0
2017-05-21T01:00:22.250Z
It certainly is close to [NORMAL SET BASIS](https://books.google.com/books?id=9NJrCQAAQBAJ&pg=PA32&lpg=PA32&dq=%22NORMAL+SET+BASIS%22&source=bl&ots=6uQ3qhz4Fp&sig=s8U9KbYWYMoxlfGgGhHcrwKs6yg&hl=en&sa=X&ved=0ahUKEwi6xent4f_TAhWB8YMKHXzNDNAQ6AEIIzAA#v=onepage&q=%22NORMAL%20SET%20BASIS%22&f=false).  That problem simply asks whether there exists any solution where $m$ is at most a given $s$ (regardless of $k$ or $\sum_i |C_i|$).  Also that problem has no constraint that $e_i\in F_i$ and $|F|=|U|$.  But it seems likely you can reduce that problem to this one.
Neal Young
<cc.complexity-theory><np-hardness><set-cover><packing>
Is the following problem NP hard?
Rhein
# Is the following problem NP hard?

(Asked by: username_0 on 2012-08-25)

Consider a collection of sets $F=\{F\_1,F\_2,\dotsc,F\_n\}$ over a base set $U=\{e\_1,e\_2,\dotsc,e\_n\}$ where $|F\_i|$ $\ll$ $n$ and $e\_i \in F\_i$, and let $k$ be a positive integer.

The goal is to find another collection of sets $C=\{C\_1,C\_2,\dotsc,C\_m\}$ over $U$ such that each $F\_i$ can be written as a union of at most $k$ $(k<<|C|)$ **mutually disjoint** sets in $C$ and also we want $\sum\_1^m |C\_j|$ to be minimal (i.e., the aggregate number of elements in all sets of $C$ should be as small as possible) .

Note that $F$ has the same size with $U$, but the size of $C$ is uncertain.

Can anyone tell whether the above problem is NP-hard? (set covering？packing？perfect covering）

Thanks for your time.

**Tags:** cc.complexity-theory, np-hardness, set-cover, packing
> **Comments:**
> **username_1**: I don't understand what the "problem" is. What is it that you want to answer?  
> **username_0**: I have re formatted the problem. Thanks. @Ankur  
> **username_1**: Is $k$ given as a part of the problem definition or do you want or is it enough to find $C$ such that the property holds for some $k$? If it is the latter, then take $C=\{ \{e_i\}, i=1...n\}$ and $k = max_i |F_i|$.  
> **username_1**: I don't know if this is indeed a known version of Set Cover, but I thought I would suggest a keyword to help you in finding the answer - a cover by mutually disjoint sets is called a "perfect cover".  
> **username_2**: Why isn't this problem trivial by setting C={U}?  
> **username_0**: Note that one constraint is "no more than k". You just remind me of another constraint since C = {F} is trivial under this statement. I'll add another constraint. Thanks.  
> **username_2**: (1) Thank you for correcting the question.  (2) What does “|F|<<n” precisely mean?  I think that you meant to write |F_i| instead of |F|, but even if I assume this, I do not know what exactly “|F_i|<<n” means.  (3) I may be picky, but why did you label [your edit](http://cstheory.stackexchange.com/posts/12403/revisions) (revision 10) as “improved formatting”?  It is not the matter of formatting.  It is a correction to the question.  
> **username_0**: |F_i|<<n,means each set in F has a size much smaller than n. Yes, it's a correction, sorry for the confusing label.  
> **username_2**: Well, my question was: what is the precise meaning of “much smaller” in this context?  
> **username_2**: Beside the precise meaning of “much smaller,” I still have trouble understanding the problem.  As is stated in revision 11, it seems to me that the optimal solution is always C=∅ or C={∅}.  If we add a constraint that C contains at least one nonempty set as an element, then C={{e}} for some element e∈U will be the optimal.  
> **username_0**: 1.Just in case that someone may make the assumption that F_i = U. So "|F_i|<<n" is given explicitly. 2.Neither C=∅ nor C={∅} works since in these two cases F_i can't be calculated as a union of sets from C.  Does the statement of problem bring ambiguity? What I want to express is that each F_i can be a union of no more than K mutually disjoint sets from C.  
> **username_2**: Please read your own question carefully.  You have never said that C must be chosen so that F_i can be written as a union of sets from C.  
> **username_2**: Now I see what you and I interpreted differently.  
> **username_2**: I had been misinterpreting “no more than k sets.”  My apologies for that.  But I hope that my edit made the question easier to understand anyway!  
> **username_3**: It is trivial if $k\ge n$.  
> **username_0**: $k<<n$. And actually in real application, $k$ is a variant rather than a constant. Each $F_i$ has its own value for $k$. @MartinB.  
> **username_0**: Can I view the NORMAL SET BASIS problem as a subproblem of the original one?  
> **username_4**: It certainly is close to [NORMAL SET BASIS](https://books.google.com/books?id=9NJrCQAAQBAJ&pg=PA32&lpg=PA32&dq=%22NORMAL+SET+BASIS%22&source=bl&ots=6uQ3qhz4Fp&sig=s8U9KbYWYMoxlfGgGhHcrwKs6yg&hl=en&sa=X&ved=0ahUKEwi6xent4f_TAhWB8YMKHXzNDNAQ6AEIIzAA#v=onepage&q=%22NORMAL%20SET%20BASIS%22&f=false).  That problem simply asks whether there exists any solution where $m$ is at most a given $s$ (regardless of $k$ or $\sum_i |C_i|$).  Also that problem has no constraint that $e_i\in F_i$ and $|F|=|U|$.  But it seems likely you can reduce that problem to this one.  

---

## 1 answers

### Answer by username_4 on 2017-05-21. Score: 2

**Lemma.** *The problem is NP-hard.*

*Proof sketch.* We disregard the constraints $|F\_i| \ll n = |U|$ in the posted problem, because, for any instance $(F,U,k)$ of the problem, the instance $(F'=F^n,U'=U^n,k)$ obtained by taking the union of $n$ independent copies of $(F,U,k)$ (where the $i$th copy of $F$ uses the $i$th copy of $U$ as its base set) is equivalent, and satisfies the constraint (it has $|F'\_i| \le n \ll n^2 = |U'|$).

We give a reduction from 3-SAT. For presentation, in the first stage of the reduction, we disregard the constraints $e\_i \in F\_i$ in the posted problem. In the second stage we describe how to meet those constraints while maintaining correctness of the reduction.

**First stage.** Fix any 3-SAT formula $\phi$. Assume WLOG that each clause has exactly three literals (each using a different variable). Produce the following instance $(F,U,k)$ of the posted problem, with $k=3$.

Let $n$ be the number of variables in $\phi$.
There are $3n+1$ elements in $U$: one element $t$ (for "true"), and, for each variable $x\_i$ in $\phi$, three elements $x\_i$, $\overline x\_i$, and $f\_i$ (for "false").

For each element in $U$ there is a singleton set containing just that element in $F$. Any solution $C$ therefore includes each of these sets, which contribute their total size $3n+1$ to the cost of $C$.

In addition, for each variable $x\_i$ in $\phi$ there is a "variable" set $\{x\_i, \overline x\_i, f\_i, t\}$ in $F$. For each clause in $\phi$ there is a "clause" set in $F$ consisting of the literals in the clause, and $t$. For example, the clause $x\_1\wedge \overline x\_2 \wedge x\_3$ yields the set $\{x\_1, \overline x\_2, x\_3, t\}$ in $F$.

**Claim 1.** *The reduction is correct: $\phi$ is satisfiable iff some solution $C$ has cost $\sum\_j |C\_j| = 5n+1$.*

*(only if)* Suppose $\phi$ is satisfiable. Construct a solution $C$ consisting of the $3n+1$ singleton sets, plus, for each variable $x\_i$, the pair consisting of the true literal and $t$. (E.g., $\{\overline x\_i, t\}$ if $x\_i$ is false.) The cost of $C$ is then $5n+1$.

Each variable set $\{x\_i, \overline x\_i, f\_i, t\}$ is the union of three sets: the pair consisting of the true literal and $t$, plus two singleton sets, one for each of the other two elements. (E.g., $\{\overline x\_i, t\}, \{x\_i\}, \{f\_i\}$.)

Each clause set (e.g. $\{x\_1, \overline x\_2, x\_3, t\}$) is the union of three sets: a pair consisting of $t$ and a true literal, plus two singleton sets, one for each of the other two literals. (E.g., $\{x\_1, t\}, \{\overline x\_2\}, \{x\_3\}$.)

*(if)* Suppose there is a solution $C$ of size $5n+1$. The solution must contain the $3n+1$ singleton sets, plus other sets of total size $2n$.

Consider first the $n$ "variable" sets, each of the form $\{x\_i, \overline x\_i, f\_i, t\}$. The set is the disjoint union of at most three sets in $C$. Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in $C$ achieves this without increasing the cost). Denote the pair $P\_i$. The pairs $P\_i$ and $P\_j$ for different variables $x\_i$ and $x\_j$ are distinct, because $P\_i$ contains $x\_i$, $\overline x\_i$, or $f\_i$ but $P\_j$ does not. Hence, the sum of the sizes of these pairs is $2n$. So these pairs are the only non-singleton sets in the solution.

Next consider the "clause" sets, e.g, $\{x\_i, \overline x\_j, x\_k, t\}$. Each such set must be the union of at most three sets in $C$, that is, up to two singleton sets and at least one pair $P\_i$, $P\_j$, or $P\_k$. By inspection of the pairs and the clause set, it must be the union of two singletons and one pair, and that pair must be of the form $\{x\_i, t\}$ or $\{\overline x\_j, t\}$ (a literal and $t$).

Hence, the following assignment satisfies $\phi$: assign true to each variable $x\_i$ such that $P\_i=\{x\_i, t\}$, assign false to each variable $x\_i$ such that $P\_i=\{\overline x\_i, t\}$, and assign the remaining variables arbitrarily.

**Stage 2.** The instance $(F,U,k=3)$ produced above does not satisfy the constraint $e\_i \in F\_i$ stated in the problem description. Fix that shortcoming as follows. Order the sets $F\_i$ and elements $e\_i$ in $U$ so that each singleton set corresponds to its element $e\_i$. Let $m$ be the number of clauses in $\phi$, so $|F|=1+4n+m$ and $|U|=1+3n$.

Let $(F', U', k'=4)$ denote the instance obtained as follows. Let $A$ be a set of $2n+2m$ new artificial elements, two for each non-singleton set in $F$. Let $U'=U\cup A$. Let $F'$ contain the singleton sets from $F$, plus, for each non-singleton set $F\_i$ in $F$, two sets $F\_i\cup \{a\_i, a\_i'\}$ and $\{a\_i,a\_i'\}$, where $a\_i$ and $a\_i'$ are two elements in $A$ chosen uniquely for $F\_i$. Now $|F'|=|U'|=1+5n+2m$ and (with the proper ordering of $F'$ and $U'$) the constraint $e'\_i\in F'\_i$ is met for each set $F'\_i$.

To finish, note that $(F',U',k'=4)$ has a solution of cost $|A|+5n+1$ iff the original instance $(F, U, k=3)$ has a solution of cost $5n+1$.

*(if)* Given any solution $C$ of cost $5n+1$ for $(F,U,k=3)$, adding the $n+m$ sets $\{a\_i, a'\_i\}$ (one for each non-singleton $F\_i$, so these partition $A$) to $C$ gives a solution to $(F', U', k'=4)$ of cost $|A|+cost(C)=|A|+5n+1$.

*(only if)* Consider any solution $C'$ for $(F', U',k=4)$ of cost $|A|+5n+1$. Consider any pair of non-singleton sets $F\_i\cup\{a\_i, a\_i'\}$ and $\{a\_i, a\_i'\}$ in $F'$. Each is the disjoint union of at most 4 sets in $C'$. By a local-exchange argument, one of these sets is $\{a\_i, a\_i'\}$ and the rest don't contain $a\_i$ or $a\_i'$ --- otherwise this property can be achieved by a local modification to the sets, without increasing the cost... (lack of detail here is why I'm calling this a proof *sketch*). So removing the $\{a\_i, a\_i'\}$ sets from $C'$ gives a solution $C$ for $(F,U,k=3)$ of cost $5n+1$. $\diamond$


---

