¿Es difícil el siguiente problema NP?

Considere una colección de conjuntos $F=\{F_1,F_2,\dotsc,F_n\}$ sobre un conjunto base $U=\{e_1,e_2,\dotsc,e_n\}$ donde $|F_i|$ $\ll$ $n$ y $e_i \in F_i$ , y sea $k$ un número entero positivo.

El objetivo es encontrar otra colección de conjuntos $C=\{C_1,C_2,\dotsc,C_m\}$ más de $U$ tal que cada $F_i$ se puede escribir como una unión de a lo sumo $k$ $(k<<|C|)$ mutuamente disjuntos establece en $C$ y también queremos $\sum_1^m |C_j|$ser mínimo (es decir, el número agregado de elementos en todos los conjuntos de $C$ debe ser lo más pequeño posible).

Tenga en cuenta que $F$ tiene el mismo tamaño que $U$ , pero el tamaño de $C$ es incierto.

¿Alguien puede decir si el problema anterior es NP-hard? (conjunto de recubrimiento？ embalaje？ recubrimiento perfecto）

Gracias por tu tiempo.

Lema El problema es NP-hard.

Bosquejo de prueba. Hacemos caso omiso de las limitaciones en el problema publicado, porque, para cualquier instancia ( F , U , k ) del problema, la instancia ( F ′ = F n , U ′ = U n , k ) se obtiene tomando la unión de n copias independientes de ( F , U , k ) (donde el $|F_i| \ll n = |U|$$(F,U,k)$$(F'=F^n,U'=U^n,k)$$n$$(F,U,k)$$i$La copia th de usa la i th copia de U como su conjunto base) es equivalente y satisface la restricción (tiene | F ′ i | ≤ n ≪ n 2 = | U ′ | ).$F$$i$$U$$|F'_i| \le n \ll n^2 = |U'|$

Le damos una reducción de 3-SAT. Para la presentación, en la primera etapa de la reducción, ignoramos las restricciones en el problema publicado. En la segunda etapa describimos cómo cumplir con esas restricciones mientras se mantiene la corrección de la reducción.$e_i \in F_i$

Primera etapa. Repara cualquier fórmula 3-SAT . Suponga WLOG que cada cláusula tiene exactamente tres literales (cada uno con una variable diferente). Produzca la siguiente instancia ( F , U , k ) del problema publicado, con k = 3 .$\phi$$(F,U,k)$$k=3$

Sea el número de variables en ϕ . Hay 3 n + 1 elementos en U : un elemento t (para "verdadero") y, para cada variable x i en ϕ , tres elementos x i , ¯ x i y f i (para "falso").$n$$\phi$$3n+1$$U$$t$$x_i$$\phi$$x_i$$\overline x_i$$f_i$

Para cada elemento en hay un conjunto singleton contiene sólo que elemento en F . Cualquier solución C incluye por lo tanto cada uno de estos conjuntos, que contribuyen a su tamaño total 3 n + 1 para el costo de C .$U$$F$$C$$3n+1$$C$

Además, para cada variable en φ hay un conjunto "variable" { x i , ¯ x i , f i , t } en F . Para cada cláusula en ϕ hay una "cláusula" establecida en F que consiste en los literales en la cláusula, y t . Por ejemplo, la cláusula x 1 ∧ ¯ x 2 ∧ x 3 produce el conjunto { x 1 , ¯ x 2 , $x_i$$\phi$$\{x_i, \overline x_i, f_i, t\}$$F$$\phi$$F$$t$$x_1\wedge \overline x_2 \wedge x_3$ en F .$\{x_1, \overline x_2, x_3, t\}$$F$

Reclamación 1. La reducción es correcta: es satisfactoria si alguna solución C ha costado ∑ j | C j | = 5 n + 1 .$\phi$$C$$\sum_j |C_j| = 5n+1$

(solo si) Suponga que es satisfactoria. Construya una solución C que consista en 3 n + 1 conjuntos singleton, más, para cada variable x i , el par que consiste en el verdadero literal y t . (Por ejemplo, { ¯ x i , t } si x i es falso.) El costo de C es entonces 5 n + 1 . $\phi$$C$$3n+1$$x_i$$t$$\{\overline x_i, t\}$$x_i$$C$$5n+1$

Cada conjunto de variables es la unión de tres conjuntos: el par que consiste en el verdadero literal yt , más dos conjuntos de singleton, uno para cada uno de los otros dos elementos. (Por ejemplo, { ¯ x i , t } , { x i } , { f i } .)$\{x_i, \overline x_i, f_i, t\}$$t$$\{\overline x_i, t\}, \{x_i\}, \{f_i\}$

Cada conjunto de cláusulas (p. Ej., ) es la unión de tres conjuntos: un par que consiste en ty un literal verdadero, más dos conjuntos de un solo tono, uno para cada uno de los otros dos literales. (Por ejemplo, { x 1 , t } , { ¯ x 2 } , { x 3 } .)$\{x_1, \overline x_2, x_3, t\}$$t$$\{x_1, t\}, \{\overline x_2\}, \{x_3\}$

(si) Suponga que hay una solución de tamaño 5 n + 1 . La solución debe contener los conjuntos de 3 n + 1 singleton, más otros conjuntos de tamaño total 2 n .$C$$5n+1$$3n+1$$2n$

Considere primero los "variables", cada uno de la forma { x i , ¯ x i , f i , t } . El conjunto es la unión de la desunión de un máximo de tres juegos en C . Sin pérdida de generalidad, es la unión disjunta de dos singletons y un par (de lo contrario, dividir conjuntos en C logra esto sin aumentar el costo). Denota el par P i . Los pares P i y P j para diferentes variables x i y x j son distintos, porque$n$$\{x_i, \overline x_i, f_i, t\}$$C$$C$$P_i$$P_i$$P_j$$x_i$$x_j$ contiene x i , ¯ x i , o f i pero P j no. Por lo tanto, la suma de los tamaños de estos pares es 2 n . Entonces, estos pares son los únicos conjuntos no singleton en la solución. $P_i$$x_i$$\overline x_i$$f_i$$P_j$$2n$

Luego considere los conjuntos de "cláusulas", por ejemplo, . Cada uno de estos conjuntos debe ser la unión de, como máximo, tres conjuntos en C , es decir, hasta dos conjuntos únicos y al menos un par P i , P j o P k . Al inspeccionar los pares y el conjunto de cláusulas, debe ser la unión de dos singletons y un par, y ese par debe tener la forma { x i , t } o { ¯ x j , t $\{x_i, \overline x_j, x_k, t\}$$C$$P_i$$P_j$$P_k$$\{x_i, t\}$$\{\overline x_j, t\}$(un literal ).$t$

Por lo tanto, la siguiente asignación satisface : asigne verdadero a cada variable x i tal que P i = { x i , t } , asigne falso a cada variable x i tal que P i = { ¯ x i , t } , y asigne el variables restantes arbitrariamente.$\phi$$x_i$$P_i=\{x_i, t\}$$x_i$$P_i=\{\overline x_i, t\}$

Etapa 2. La instancia $(F,U,k=3)$ producida anteriormente no satisface la restricción establecida en la descripción del problema. Arregle esa deficiencia de la siguiente manera. Ordena los conjuntos F i y los elementos e i en U para que cada conjunto singleton corresponda a su elemento e i . Sea m el número de cláusulas en ϕ , entonces | F | = 1 + 4 n $e_i \in F_i$$F_i$$e_i$$U$$e_i$$m$$\phi$ y | U | = 1 + 3 n .$|F|=1+4n+m$$|U|=1+3n$

Sea denotar la instancia obtenida de la siguiente manera. Deje que A sea un conjunto de 2 n + 2 m nuevos elementos artificiales, dos para cada conjunto no singleton en F . Dejar que T ' = T ∪ A . Supongamos que F ' contiene los conjuntos singleton de F , además, para cada conjunto no singleton F i en F , dos conjuntos F i ∪ { $(F', U', k'=4)$$A$$2n+2m$$F$$U'=U\cup A$$F'$$F$$F_i$$F$ y { a i , a ′ i } , donde a i y a ′ i son dos elementos en A elegidos exclusivamente para F i . Ahora | F ′ | = | U ′ | = 1 + 5 n + 2 my (con el orden adecuado de F ' y U ' ) la restricción$F_i\cup \{a_i, a_i'\}$$\{a_i,a_i'\}$$a_i$$a_i'$$A$$F_i$$|F'|=|U'|=1+5n+2m$$F'$$U'$ se cumple para cada conjuntoF ′ i .$e'_i\in F'_i$$F'_i$

Para finalizar, tenga en cuenta que tiene una solución de costo | A | + 5 n + 1 si la instancia original ( F , U , k = 3 ) tiene una solución de costo 5 n + 1 .$(F',U',k'=4)$$|A|+5n+1$$(F, U, k=3)$$5n+1$

(si) Dado cualquier solución de costo 5 n + 1 para ( F , U , k = 3 ) , la adición de los n + m conjuntos { a i , un ' i } (una para cada no singleton F i , por lo que estos la partición A ) a C da una solución a ( F ′ , U ′ , k ′ = 4 ) del costo$C$$5n+1$$(F,U,k=3)$$n+m$$\{a_i, a'_i\}$$F_i$$A$$C$$(F', U', k'=4)$ .$|A|+cost(C)=|A|+5n+1$

(solo si) Considere cualquier solución para ( F ′ , U ′ , k = 4 ) de costo | A | + 5 n + 1 . Considere cualquier par de conjuntos no singleton F i ∪ { a i , a ′ i } y { a i , a ′ i } en F ′ . Cada uno es la unión disjunta de, como máximo, 4 conjuntos en $C'$$(F', U',k=4)$$|A|+5n+1$$F_i\cup\{a_i, a_i'\}$$\{a_i, a_i'\}$$F'$ . Por un argumento de intercambio local, uno de estos conjuntos es { a i , a ′ i } y el resto no contiene un i o a ′ i --- de lo contrario, esta propiedad puede lograrse mediante una modificación local de los conjuntos, sin aumentar el costo ... (falta de detalles aquí es por eso que llamo a esto unbosquejo deprueba). Entonces, eliminar los conjuntos { a i , a ′ i } de C ′ da una solución C para ( F , U $C'$$\{a_i, a_i'\}$$a_i$$a_i'$$\{a_i, a_i'\}$$C'$$C$ de costo 5 n + 1 . $(F,U,k=3)$$5n+1$$\diamond$