# Is the following problem NP hard?

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.

• I don't understand what the "problem" is. What is it that you want to answer? – Ankur Aug 25 '12 at 15:02
• Why isn't this problem trivial by setting C={U}? – Tsuyoshi Ito Aug 26 '12 at 14:09
• 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 Aug 26 '12 at 16:52
• 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 Aug 27 '12 at 14:44
• Can I view the NORMAL SET BASIS problem as a subproblem of the original one? – Rhein Sep 2 '12 at 11:11

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$