O seguinte problema é NP difícil?

15

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| nneiFieiFik 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.

Rhein
fonte
Não entendo qual é o "problema". O que você quer responder?
Ankur
4
Por que esse problema não é trivial ao definir C = {U}?
Tsuyoshi Ito
6
Além do significado preciso de "muito menor", ainda tenho problemas para entender o problema. Como afirmado na revisão 11, parece-me que a solução ideal é sempre C = ∅ ou C = {∅}. Se adicionarmos uma restrição de que C contém pelo menos um conjunto não vazio como um elemento, C = {{e}} para algum elemento e∈U será o ideal.
Tsuyoshi Ito
1
Por favor, leia sua própria pergunta com cuidado. Você nunca disse que C deve ser escolhido para que F_i possa ser escrito como uma união de conjuntos de C. #
Tsuyoshi Ito
1
Posso visualizar o problema NORMAL SET BASIS como um subproblema do original?
Rhein

Respostas:

2

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)ia 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 | ).FiU|Fi|nn2=|U|

Damos uma redução de 3-SAT. Para apresentação, no primeiro estágio da redução, desconsideramos as restrições e iF i no problema publicado. No segundo estágio, descrevemos como atender a essas restrições, mantendo a correção da redução.eiFi

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+1Utxiϕxix¯¯¯ifi

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 .UFC3n+1C

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 2x 3 rendimentos do conjunto { x 1 , ¯ x 2 , xxiϕ{xi,x¯¯¯i,fi,t}FϕFtx1x¯¯¯2x33 , 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 .ϕCj|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 . ϕC3n+1xit{x¯¯¯i,t}xiC5n+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 .C5n+13n+12n

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}CCPiPiPjxixjP 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. Pixix¯¯¯ifiPj2n

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}CPiPjPk{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 iF 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=UA. Let F contain the singleton sets from F, plus, for each non-singleton set Fi in F, two sets Fi{ai,ai} and {ai,ai}, where ai and ai 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 eiFi is met for each set Fi.

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,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
fonte