Considere uma coleção de conjuntos em um conjunto de base que e , e deixá- kF={F1,F2,…,Fn}F={F1,F2,…,Fn}U={e1,e2,…,en}U={e1,e2,…,en}|Fi||Fi| ≪≪ nnei∈Fiei∈Fik ser um número inteiro positivo.
O objetivo é encontrar uma outra coleção de conjuntos C = { C 1 , C 2 , ... , C m }C={C1,C2,…,Cm} mais de UU tal que cada F iFi pode ser escrita como uma união de, no máximo, k k ( k < < | C | )(k<<|C|) mutuamente disjuntos define em CC e também queremos ∑ m 1 | C j | ∑m1|Cj|ser mínimo (isto é, o número agregado de elementos em todos os conjuntos deCC deve ser o menor possível).
Observe que tem o mesmo tamanho de , mas o tamanho de é incerto.FFUUCC
Alguém pode dizer se o problema acima é NP-difícil? (conjunto de cobertura? embalagem covering cobertura perfeita)
Obrigado pelo seu tempo.
Respostas:
Lema. O problema é NP-difícil.
Esboço de prova. Nós desconsideramos as restrições | F i | « N = | U | no problema publicado, porque, para qualquer instância ( F , U , k ) do problema, a instância ( F ′ = F n , U ′ = U n , k ) obtida através da união de n cópias independentes de ( F , U , k ) (onde i|Fi|≪n=|U| (F,U,k) (F′=Fn,U′=Un,k) n (F,U,k) i a cópia de F usa a i- cópia de U como seu conjunto base) é equivalente e satisfaz a restrição (possui | F ′ i | ≤ n ≪ n 2 = | U ′ | ).F i U |F′i|≤n≪n2=|U′|
Damos uma redução de 3-SAT. Para apresentação, no primeiro estágio da redução, desconsideramos as restrições e i ∈ F i no problema publicado. No segundo estágio, descrevemos como atender a essas restrições, mantendo a correção da redução.ei∈Fi
Primeira etapa. Corrija qualquer fórmula 3-SAT ϕ . Suponha ao WLOG que cada cláusula tenha exatamente três literais (cada um usando uma variável diferente). Produza a seguinte instância ( F , U , k ) do problema postado, com k = 3 .ϕ (F,U,k) k=3
Seja n o número de variáveis em ϕ . Existem 3 N + 1 elementos em L : um elemento t (para "verdadeiro"), e, para cada variável x i em φ , três elementos x i , ¯ x i , e f i (para "falso").n ϕ 3n+1 U t xi ϕ xi x¯¯¯i fi
Para cada elemento em L , existe um conjunto Singleton contendo apenas o elemento em M . Qualquer solução de C inclui, por conseguinte, cada um destes conjuntos, os quais contribuem com o seu tamanho total de 3 n + 1 para o custo de C .U F C 3n+1 C
Além disso, para cada variável x i em φ existe um conjunto "variável" { x i , ¯ x i , f i , t } em F . Para cada cláusula φ existe um conjunto "cláusula" em F consistindo dos literais na cláusula, e t . Por exemplo, a cláusula x 1 ∧ ¯ x 2 ∧ x 3 rendimentos do conjunto { x 1 , ¯ x 2 , xxi ϕ {xi,x¯¯¯i,fi,t} F ϕ F t x1∧x¯¯¯2∧x3 3 , t } em F .{x1,x¯¯¯2,x3,t} F
Reivindicação 1. A redução está correta: ϕ é satisfatória se alguma solução C custar ∑ j | C j | = 5 n + 1 .ϕ C ∑j|Cj|=5n+1
(apenas se) Suponha que ϕ seja satisfatório. Construir uma solução de C que consiste nos 3 n + 1 grupos Singleton, além disso, para cada variável x i , a par consistindo da verdadeira literal e t . (Por exemplo, { ¯ x i , t } se x i for falso.) O custo de C é então 5 n + 1 .ϕ C 3n+1 xi t {x¯¯¯i,t} xi C 5n+1
Cada conjunto de variáveis { x i , ¯ x i , f i , t } é a união de três conjuntos: a par consistindo da verdadeira literal e T , mais dois conjuntos únicos, um para cada um dos outros dois elementos. (Por exemplo, { ¯ x i , t } , { x i } , { f i } .){xi,x¯¯¯i,fi,t} t {x¯¯¯i,t},{xi},{fi}
Cada conjunto de cláusulas (por exemplo, { x 1 , ¯ x 2 , x 3 , t } ) é a união de três conjuntos: um par que consiste em te literal literal, além de dois conjuntos singleton, um para cada um dos outros dois literais. (Por exemplo, { x 1 , t } , { ¯ x 2 } , { x 3 } .){x1,x¯¯¯2,x3,t} t {x1,t},{x¯¯¯2},{x3}
(se) Suponha que exista uma solução C de tamanho 5 n + 1 . A solução deve conter os 3 n + 1 conjuntos singleton, além de outros conjuntos de tamanho total 2 n .C 5n+1 3n+1 2n
Considere primeiro os n conjuntos de "variáveis", cada um da forma { x i , ¯ x i , f i , t } . O conjunto é a união disjunta de no máximo três conjuntos em C . Sem perda de generalidade, é a união disjunta de dois singletons e um par (caso contrário, a divisão de conjuntos em C consegue isso sem aumentar o custo). Indique o par P i . O pares P i e P j por diferentes variáveis x i e x j são distintos, porquen {xi,x¯¯¯i,fi,t} C C Pi Pi Pj xi xj P i contém x i , ¯ x i , ou f i, mas P j não. Portanto, a soma dos tamanhos desses pares é 2 n . Portanto, esses pares são os únicos conjuntos não singleton na solução. Pi xi x¯¯¯i fi Pj 2n
A seguir, considere os conjuntos de "cláusulas", por exemplo, { x i , ¯ x j , x k , t } . Cada um desses conjuntos deve ser a união de no máximo três conjuntos em C , ou seja, até dois conjuntos singleton e pelo menos um par P i , P j ou P k . Pela inspeção dos pares e do conjunto de cláusulas, deve ser a união de dois singletons e um par, e esse par deve ter a forma { x i , t } ou { ¯ x j , t }{xi,x¯¯¯j,xk,t} C Pi Pj Pk {xi,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 xi such that Pi={¯xi,t}, and assign the remaining variables arbitrarily.
Fase 2. A instância ( F , U , k = 3 ) produzida acima não satisfaz a restrição e i ∈ F i declarada na descrição do problema. Corrija essa falha da seguinte maneira. Ordene os conjuntos F i e os elementos e i em U para que cada conjunto singleton corresponda ao seu elemento e i . Seja m o número de cláusulas em ϕ , então | F | = 1 + 4 n +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∪A. Let F′ contain the singleton sets from F, plus, for each non-singleton set Fi in F, two sets Fi∪{ai,a′i} and {ai,a′i}, where ai and a′i are two elements in A chosen uniquely for Fi. Now |F′|=|U′|=1+5n+2m and (with the proper ordering of F′ and U′) the constraint e′i∈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 {ai,a′i} (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,a′i} and {ai,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 {ai,a′i} and the rest don't contain ai 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 {ai,a′i} sets from C′ gives a solution C for (F,U,k=3) of cost 5n+1. ⋄
fonte