Ist das folgende Problem NP schwer?

Betrachten wir eine Sammlung von Sätzen $F=\{F_1,F_2,\dotsc,F_n\}$ über einen Basissatz wo und , und sei eine positive ganze Zahl.$U=\{e_1,e_2,\dotsc,e_n\}$$|F_i|$ $\ll$ $n$$e_i \in F_i$$k$

Das Ziel ist ein weitere Sammlung von Sätzen zu finden $C=\{C_1,C_2,\dotsc,C_m\}$ über $U$ , so dass jedes $F_i$ kann höchstens als eine Vereinigung von geschrieben werden $k$ $(k<<|C|)$ disjunktem setzt in $C$ und wir wollen auch $\sum_1^m |C_j|$minimal sein (dh die Gesamtzahl der Elemente in allen Sätzen von $C$ sollte so klein wie möglich sein).

Beachten Sie, dass $F$ dieselbe Größe wie $U$ hat, die Größe von $C$ jedoch ungewiss ist.

Kann jemand sagen, ob das oben genannte Problem NP-schwer ist? (set abdeckung, verpackung, perfekte abdeckung,

Vielen Dank für Ihre Zeit.

Lemma. Das Problem ist NP-schwer.

Proof-Skizze. Wir ignorieren die Einschränkungen | F i | ≪ n = | U | in dem gesendeten Problem, weil für jede Instanz ( F , U , k ) des Problems die Instanz ( F ' = F n , U ' = U n , k ) erhalten wird, indem die Vereinigung von n unabhängigen Kopien von ( F , U , k ) (wo das $|F_i| \ll n = |U|$$(F,U,k)$$(F'=F^n,U'=U^n,k)$$n$$(F,U,k)$$i$Die i - te Kopie von F, die die i- te Kopie von U als Basismenge verwendet, ist äquivalent und erfüllt die Bedingung (sie hat | F ' i | ≤ n ≪ n 2 = | U ' | ).$F$$i$$U$$|F'_i| \le n \ll n^2 = |U'|$

Wir geben eine Ermäßigung von 3-SAT. Für die Darstellung werden in der ersten Stufe der Reduktion die Einschränkungen e i ∈ F i in dem gestellten Problem ignoriert . In der zweiten Stufe beschreiben wir, wie diese Einschränkungen erfüllt werden können, während die Korrektheit der Reduktion erhalten bleibt.$e_i \in F_i$

Erste Stufe. Fixiere eine beliebige 3-SAT-Formel ϕ . Angenommen, WLOG hat für jede Klausel genau drei Literale (wobei jeder eine andere Variable verwendet). Erstellen Sie die folgende Instanz ( F , U , k ) des angegebenen Problems mit k = 3 .$\phi$$(F,U,k)$$k=3$

Sei n die Anzahl der Variablen in ϕ . Es gibt 3 n + 1 Elemente in U : ein Element t (für "true"), und für jede Variable x i in φ , drei Elemente x i , ¯ x i und f i (für "false").$n$$\phi$$3n+1$$U$$t$$x_i$$\phi$$x_i$$\overline x_i$$f_i$

Für jedes Element in U gibt es eine Singleton-Menge, die nur dieses Element in F enthält . Jede Lösung C enthält daher jede dieser Mengen, die ihre Gesamtgröße 3 n + 1 zu den Kosten von C beitragen .$U$$F$$C$$3n+1$$C$

Zusätzlich gibt es für jede Variable x i in ϕ eine "Variable", die in F { x i , ¯ x i , f i , t } gesetzt ist . Für jede Klausel in ϕ gibt es eine "Klausel" in F, die aus den Literalen in der Klausel besteht, und t . Zum Beispiel kann die Klausel x 1 ∧ ¯ x 2 ∧ x 3 liefert die eingestellte { 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$3 , t } in F .$\{x_1, \overline x_2, x_3, t\}$$F$

Behauptung 1. Die Reduktion ist richtig: ϕ ist erfüllbar, wenn eine Lösung C ∑ j | kostet C j | = 5 n + 1 .$\phi$$C$$\sum_j |C_j| = 5n+1$

(nur wenn) Angenommen, ϕ ist erfüllbar. Konstruieren Sie eine Lösung C, die aus den 3 n + 1 Singleton-Mengen und für jede Variable x i aus dem wahren Literal und t besteht . (ZB { ¯ x i , t }, wenn x i falsch ist.) Die Kosten für C betragen dann 5 n + 1 . $\phi$$C$$3n+1$$x_i$$t$$\{\overline x_i, t\}$$x_i$$C$$5n+1$

Jede Variablenmenge { x i , ¯ x i , f i , t } ist die Vereinigung von drei Mengen: das Paar, bestehend aus dem wahren Literal und t , plus zwei Singleton-Mengen, eine für jedes der beiden anderen Elemente. (ZB { ¯ x i , t } , { x i } , { f i } .)$\{x_i, \overline x_i, f_i, t\}$$t$$\{\overline x_i, t\}, \{x_i\}, \{f_i\}$

Jede Klauselmenge (zB { x 1 , ¯ x 2 , x 3 , t } ) ist die Vereinigung von drei Mengen: Ein Paar bestehend aus t und einem wahren Literal plus zwei Singleton-Mengen, eine für jede der beiden anderen Literale. (ZB { x 1 , t } , { ¯ x 2 } , { x 3 } .)$\{x_1, \overline x_2, x_3, t\}$$t$$\{x_1, t\}, \{\overline x_2\}, \{x_3\}$

(if) Angenommen, es gibt eine Lösung C der Größe 5 n + 1 . Die Lösung muss die Singleton-Mengen 3 n + 1 sowie weitere Mengen mit einer Gesamtgröße von 2 n enthalten .$C$$5n+1$$3n+1$$2n$

Betrachten wir zunächst die n "variable" Sätze, die jeweils der Form { x i , ¯ x i , f i , t } . Das Set ist die disjunkte Vereinigung von höchstens drei Sätzen in C . Ohne Verlust der Allgemeinheit handelt es sich um die disjunkte Vereinigung von zwei Singuletten und einem Paar (andernfalls wird dies durch Aufteilen von Mengen in C erreicht, ohne die Kosten zu erhöhen). Bezeichne das Paar P i . Die Paare P i und P j für verschiedene Variablen x i und x j sind unterschiedlich, weil$n$$\{x_i, \overline x_i, f_i, t\}$$C$$C$$P_i$$P_i$$P_j$$x_i$$x_j$$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$