15
$\begingroup$

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.

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

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.