Czy następujący problem NP jest trudny?

15

Rozważmy zbiór zbiorów F = { F 1 , F 2 , , F n } nad zestawem podstawowym U = { e 1 , e 2 , , e n } gdzie | F i | « N i e iF I i pozwolić K jest dodatnią liczbą całkowitą.F={F1,F2,,Fn}U={e1,e2,,en}|Fi| neiFik

Celem jest, aby znaleźć inny zbiór zestawów C = { C 1 , C 2 , ... , C m } nad U takie, że każdy F i może być zapisany jako unii co najwyżej k ( k < < | C | ) wzajemnie rozłączne ustawia w C i też chcemy m 1 | C j | być minimalna (tj. łączna liczba elementów we wszystkich zestawach CC={C1,C2,,Cm}UFik (k<<|C|) Cm1|Cj|C powinien być jak najmniejszy).

Zauważ, że F ma taki sam rozmiar jak U , ale rozmiar C jest niepewny.FUC

Czy ktoś może powiedzieć, czy powyższy problem dotyczy NP? (zestaw osłon? opakowanie? idealne pokrycie)

Dziękuję za Twój czas.

Rhein
źródło
Nie rozumiem na czym polega „problem”. Na co chcesz odpowiedzieć?
Ankur,
4
Dlaczego ten problem nie jest trywialny, ustawiając C = {U}?
Tsuyoshi Ito
6
Oprócz dokładnego znaczenia słowa „dużo mniejszy” nadal mam problem ze zrozumieniem problemu. Jak stwierdzono w wersji 11, wydaje mi się, że optymalnym rozwiązaniem jest zawsze C = ∅ lub C = {∅}. Jeśli dodamy ograniczenie, że C zawiera co najmniej jeden niepusty zestaw jako element, wówczas C = {{e}} dla jakiegoś elementu e∈U będzie optymalny.
Tsuyoshi Ito
1
Przeczytaj uważnie własne pytanie. Nigdy nie mówiłeś, że C musi być wybrany, aby F_i można było zapisać jako połączenie zbiorów z C.
Tsuyoshi Ito
1
Czy mogę postrzegać problem ZESTAWU NORMALNEGO jako podproblem pierwotnego?
Rhein

Odpowiedzi:

2

Lemat. Problem jest trudny NP.

Szkic próbny. Nie uwzględniamy ograniczeń | F i | n = | U | w opublikowanym problemie, ponieważ dla dowolnej instancji ( F , U , k ) problemu, instancja ( F = F n , U = U n , k ) uzyskana przez wzięcie n niezależnych kopii ( F , U tej kopii F używa i|Fi|n=|U|(F,U,k)(F=Fn,U=Un,k)n , k ) (gdzie i(F,U,k)iFi tej kopii U, ponieważ jej zbiór podstawowy jest równoważny i spełnia ograniczenie (ma | F i |n n 2 = | U | ).U|Fi|nn2=|U|

Dajemy redukcję z 3-SAT. Do prezentacji w pierwszym etapie redukcji pomijamy ograniczenia e iF i w opublikowanym problemie. W drugim etapie opisujemy, jak sprostać tym ograniczeniom, zachowując przy tym poprawność redukcji.eiFi

Pierwszy etap. Napraw dowolną formułę 3-SAT ϕ . Załóżmy WLOG, że każda klauzula ma dokładnie trzy literały (każda używa innej zmiennej). Wywołaj następujący przykład ( F , U , k ) opublikowanego problemu, przy k = 3 .ϕ(F,U,k)k=3

Niech n będzie liczbą zmiennych w ϕ . Istnieją 3 n + 1 w elementach U : jeden element t (na "true"), a dla każdej zmiennej x I w cp trzy elementy x i , Ż x Inϕ3n+1Utxiϕxix¯¯¯i , a F I (na "fałsz").fi

Dla każdego elementu U jest zestaw zawierający tylko pojedyncza że element F . Każde rozwiązanie C obejmuje zatem każdy z tych zestawów, które przyczyniają się do ich całkowitego rozmiaru 3 n +UFC 1 do kosztów C .3n+1C

Dodatkowo, dla każdej zmiennej x I w cp jest "zmienna" zestaw { x I , Ż x I , F I , T } w F . Dla każdego punktu w cp jest „punkt” ustawione w F składający się literałach w pkt i t . Na przykład, klauzula x 1¯ x 2x 3 zwraca zbiór { x 1 , ¯ x 2 , xxiϕ{xi,x¯¯¯i,fi,t}FϕFtx1x¯¯¯2x3 3 , t }{x1,x¯¯¯2,x3,t} w F .F

Twierdzenie 1. Redukcja jest poprawna: ϕ jest satysfakcjonująca, jeśli niektóre rozwiązanie C ma koszt j | C j | = 5 n + 1 .ϕCj|Cj|=5n+1

(tylko jeśli) Załóżmy, że ϕ jest zadowalająca. Skonstruuj rozwiązanie C składające się z 3 zestawów singletonów 3 n + 1 , plus, dla każdej zmiennej x i , parę składającą się z prawdziwego literału it . (Np. { ¯ x i , t } jeśli x i jest fałszem.) Koszt C wynosi wtedy 5ϕC3n+1xit{x¯¯¯i,t}xiC n + 1 . 5n+1

Każdy zestaw zmiennych { x i , ¯ x i , f i , t } jest sumą trzech zbiorów: pary składającej się z prawdziwego literału it oraz dwóch zestawów singletonów, po jednym dla każdego z pozostałych dwóch elementów. (Np. { ¯ x i , t } , { x i } , { f i } .){xi,x¯¯¯i,fi,t}t{x¯¯¯i,t},{xi},{fi}

Każdy zestaw punkt (np { x 1 , Ż x 2 , x 3 , t } ) jest sumą trzech grup: parę składającą się z t i prawdziwego dosłownym plus dwa zestawy pojedynczych, po jednym dla każdej z dwóch literałach. (Np. { X 1 , t } , { ¯ x 2 } , { x 3 } .){x1,x¯¯¯2,x3,t}t{x1,t},{x¯¯¯2},{x3}

(if) Suppose there is a solution CC of size 5n+15n+1. The solution must contain the 3n+13n+1 singleton sets, plus other sets of total size 2n2n.

Consider first the nn "variable" sets, each of the form {xi,¯xi,fi,t}{xi,x¯¯¯i,fi,t}. The set is the disjoint union of at most three sets in CC. Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in CC achieves this without increasing the cost). Denote the pair PiPi. The pairs PiPi and PjPj for different variables xixi and xjxj are distinct, because PiPi contains xixi, ¯xix¯¯¯i, or fifi but PjPj does not. Hence, the sum of the sizes of these pairs is 2n2n. So these pairs are the only non-singleton sets in the solution.

Next consider the "clause" sets, e.g, {xi,¯xj,xk,t}{xi,x¯¯¯j,xk,t}. Each such set must be the union of at most three sets in CC, that is, up to two singleton sets and at least one pair PiPi, PjPj, or PkPk. 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 {xi,t}{xi,t} or {¯xj,t}{x¯¯¯j,t} (a literal and tt).

Hence, the following assignment satisfies ϕϕ: assign true to each variable xixi such that Pi={xi,t}Pi={xi,t}, assign false to each variable xixi such that Pi={¯xi,t}Pi={x¯¯¯i,t}, and assign the remaining variables arbitrarily.

Stage 2. The instance (F,U,k=3)(F,U,k=3) produced above does not satisfy the constraint eiFieiFi stated in the problem description. Fix that shortcoming as follows. Order the sets FiFi and elements eiei in UU so that each singleton set corresponds to its element eiei. Let mm be the number of clauses in ϕϕ, so |F|=1+4n+m|F|=1+4n+m and |U|=1+3n|U|=1+3n.

Let (F,U,k=4)(F,U,k=4) denote the instance obtained as follows. Let AA be a set of 2n+2m2n+2m new artificial elements, two for each non-singleton set in FF. Let U=UAU=UA. Let FF contain the singleton sets from FF, plus, for each non-singleton set FiFi in FF, two sets Fi{ai,ai}Fi{ai,ai} and {ai,ai}{ai,ai}, where aiai and aiai are two elements in AA chosen uniquely for FiFi. Now |F|=|U|=1+5n+2m|F|=|U|=1+5n+2m and (with the proper ordering of FF and UU) the constraint eiFieiFi is met for each set FiFi.

To finish, note that (F,U,k=4)(F,U,k=4) has a solution of cost |A|+5n+1|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 {ai,ai} (one for each non-singleton Fi, 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 Fi{ai,ai} and {ai,ai} in F. Each is the disjoint union of at most 4 sets in C. By a local-exchange argument, one of these sets is {ai,ai} and the rest don't contain ai or ai --- 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 {ai,ai} sets from C gives a solution C for (F,U,k=3) of cost 5n+1.

Neal Young
źródło