Apakah NP masalah berikut ini sulit?

Pertimbangkan kumpulan set $F=\{F_1,F_2,\dotsc,F_n\}$ atas set dasar $U=\{e_1,e_2,\dotsc,e_n\}$ mana $|F_i|$ $\ll$ $n$ dan $e_i \in F_i$ , dan biarkan $k$ menjadi bilangan bulat positif.

Tujuannya adalah untuk menemukan koleksi lain dari set $C=\{C_1,C_2,\dotsc,C_m\}$ lebih $U$ sehingga setiap $F_i$ dapat ditulis sebagai kesatuan paling $k$ $(k<<|C|)$ saling disjoint set dalam $C$ dan juga kita inginkan $\sum_1^m |C_j|$menjadi minimal (yaitu jumlah elemen agregat di semua set $C$ harus sekecil mungkin).

Perhatikan bahwa $F$ memiliki ukuran yang sama dengan $U$ , tetapi ukuran $C$ tidak pasti.

Adakah yang tahu apakah masalah di atas adalah NP-hard? (set penutup？ pengepakan？ penutup sempurna）

Terima kasih atas waktunya.

Kata pengantar singkat. Masalahnya adalah NP-hard.

Sketsa bukti. Kami mengabaikan kendala | F i | ≪ n = | U | dalam masalah yang diposting, karena, untuk setiap instance ( F , U , k ) dari masalah, instance ( F ′ = F n , U ′ = U n , k ) diperoleh dengan mengambil gabungan dari n salinan independen dari ( F , U , k ) (di mana $|F_i| \ll n = |U|$$(F,U,k)$$(F'=F^n,U'=U^n,k)$$n$$(F,U,k)$$i$ salinan F menggunakan $F$$i$ th menyalin dari U sebagai set basis) adalah setara, dan memenuhi kendala (memiliki | F ' i | ≤ n « n 2 = | U ' | ).$U$$|F'_i| \le n \ll n^2 = |U'|$

Kami memberikan pengurangan dari 3-SAT. Untuk presentasi, pada tahap pertama reduksi, kami mengabaikan kendala e i ∈ F i dalam masalah yang diposting. Pada tahap kedua kami menjelaskan bagaimana memenuhi kendala tersebut sambil mempertahankan kebenaran reduksi.$e_i \in F_i$

Tahap pertama. Perbaiki formula 3-SAT ϕ . Asumsikan WLOG bahwa setiap klausa memiliki tepat tiga literal (masing-masing menggunakan variabel yang berbeda). Hasilkan contoh berikut ( F , U , k ) dari masalah yang diposting, dengan k = 3 .$\phi$$(F,U,k)$$k=3$

Biarkan n menjadi jumlah variabel dalam ϕ . Ada 3 n + 1 elemen dalam U : satu elemen t (untuk "benar"), dan, untuk setiap variabel x i di φ , tiga elemen x i , ¯ x i , dan f i (untuk "false").$n$$\phi$$3n+1$$U$$t$$x_i$$\phi$$x_i$$\overline x_i$$f_i$

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$