Complexidade de encontrar o número máximo de conjuntos disjuntos em pares

9

Suponha que eu tenha conjuntos com elementos extraídos de possíveis. Cada conjunto é do tamanho ( ), onde os conjuntos podem se sobrepor. Quero determinar se os dois problemas a seguir estão completos ou não com NP:r n n < rPrnn<r

Problema A. Existem ( ) conjuntos distintos dentro dos conjuntos (ou seja, sua interseção em pares está vazia)?1 M P PM1MPP

Problema B. Agora, elementos ( ) podem ser escolhidos de cada conjunto. Existem ( ) conjuntos distintos de tamanho cada um dentro dos conjuntos ? Observe que apenas um conjunto de elementos pode ser obtido de cada conjunto de elementos.k < n L 1 L P k P k nkk<nL1LPkPkn

Observação : Estou interessado principalmente no caso em que é fixo ( ).n 2 , k 2k,nn2,k2

Penso que o Problema A pode ser pensado como um problema de correspondência de hiper-grafos uniformes partites. Ou seja, temos os elementos de como vértices e cada hiper-aresta contém um subconjunto de vértices do gráfico.r r nnrrn

  1. No problema de correspondência do hipergrafo uniforme partite NP-completo?rnr

  2. Penso que o Problema B é equivalente a encontrar o número de hiper-bordas distintas da cardinalidade retiradas das hiper-bordas da cardinalidade . Essa versão restrita (no sentido de que cada conjunto de cardinalidade- é extraída de um conjunto pré-escolhido de elementos em vez de extraída arbitrariamente de elementos) do Problema A NP-completo?n k n rknknr

Exemplo ( ):n=3,r=5,P=3

B = { 2 , 3 , 4 } C = { 3 , 4 , 5 }A={1,2,3} , ,B={2,3,4}C={3,4,5}

Se , existe apenas um conjunto distinto, que é ou ou , já que cada um dos pares , , possui cruzamento vazio.M = 1 A B C ( A , B ) ( A , C ) ( B , C )k=n=3M=1ABC(A,B)(A,C)(B,C)

Se , temos conjuntos distintos: uma solução é , (subconjuntos de e ).L = 2 { 1 , 2 } { 3 , 4 } A Bk=2L=2{1,2}{3,4}AB

MJK
fonte

Respostas:

2

Este é um caso especial do Problema Máximo de Embalagem de Conjuntos e os problemas A e B são NP-Completos . Observe que o problema é simplesmente um problema de correspondência se e também é fácil se . Então, eu assumirei .n = 1 n 3n=2n=1n3

Em vez de fazer a pergunta,

Existem conjuntos disjuntos entre os conjuntos ?PMP

Vamos fazer a seguinte pergunta

Qual é o número máximo de conjuntos disjuntos que podemos obter dos conjuntos ?P

É claro que, se a segunda pergunta for respondida em tempo polinomial, a mesma será a primeira, pois tudo o que precisamos fazer é comparar esse valor máximo com e gerar SIM se for menor ou igual a esse máximo e NÃO de outra forma.MMM

Além disso, se a primeira pergunta for respondida em tempo polinomial, a segunda também será, pois podemos usar a pesquisa binária em e obter a resposta para a segunda pergunta e adicionar apenas um fator deO ( log M )MO(logM)

Portanto, podemos concluir que as duas perguntas são equivalentes. ou seja, a pergunta 1 é passível de solução polilomial se e somente se a pergunta 2 também for.

Também está claro que os problemas estão no NP, pois podemos facilmente verificar se os conjuntos emitidos são disjuntos.M

Portanto, a questão agora é como reduzimos um problema conhecido de NP-Hard a isso? Para fazer isso, reduzimos o problema de empacotamento máximo definido . Vou simplesmente focar no problema A, já que o problema B pode ser facilmente difícil definindok=n1

Considere uma instância arbitrária do problema máximo conjunto de embalagem . Observe que a única diferença entre o problema A e o problema de embalagem máxima do conjunto original é que, no problema A, o tamanho dos conjuntos deve ser igual. Vamos ser a cardinalidade máxima entre todos os conjuntos em . Se todo conjunto em tem a mesma cardinalidade, estamos prontos e o problema de cobertura do conjunto é exatamente o problema A. Agora, suponha que, para algum conjunto , tenhamos . Nós simplesmente adicionar elementos para que não são elementos de qualquer conjunto em . Repetimos esse processo até que todos os conjuntosTtTTSiT|Si|<t(t|Si|)SiTSiTtem o mesmo tamanho. É claro que a adição de novos elementos dessa maneira não altera o tamanho do número máximo de conjuntos disjuntos.

Portanto, se pudermos resolver o problema em tempo polinomial, podemos resolver o problema de empacotamento máximo definido em tempo polinomial, pois tudo o que precisamos fazer é remover os elementos extras que adicionamos e isso não altera o tamanho da número máximo de conjuntos disjuntos em .AT

EDIT - Algumas informações adicionais sobre o problema B

Suponha que o problema B tenha uma solução de tempo polinomial, agora considere uma instância arbitrária do problema A com elementos por conjunto. Agora vamos adicionar um elemento fictício para cada conjunto em . Agora fazemos a seguinte pergunta.TndT

Qual é o número máximo de conjuntos disjuntos que podemos obter retirando elementos de cada conjunto?n

Agora sabemos que entre os conjuntos no máximo, no máximo um deles pode conter o elemento fictício; portanto, se a resposta que obtivermos como máximo for , o número máximo real de conjuntos na instância (nosso problema original A) é ou , mas isso fornece uma aproximação constante do fator para a gaxeta máxima definida. E essa aproximação só é possível se . Então o problema B também é difícil.MTM(M1)P=NP

Obinna
fonte
Em relação ao problema B: se você adicionar um elemento fictício a todos os conjuntos do Problema A, obterá conjuntos de tamanho . No exemplo que aparece na minha pergunta ( ), você verá que o número máximo de conjuntos disjuntos de tamanho é 3: . No entanto, a solução para o problema A é que existe apenas um conjunto. Em outras palavras, eu não vejo como uma solução para o problema B dá um fator de aproximação constante para o Problema A.n+1n=3,P=3n1=2{1,d},{2,3},{4,5}
MJK
Se você adicionar o elemento fictício, terá os conjuntos e . Esta nova instância com é a instância do problema Uma Estamos interessados em. Agora, execute o algoritmo B suposto nesses conjuntos, ou seja, e . É isso que eu estou dizendo. Observe que o problema se reduz a encontrar uma correspondência máxima se ou . C = { 3 , 4 , 5 , d } n = 4 n = 4 k = 3 n = 2 k = 2A={1,2,3,d},B={2,3,4,d}C={3,4,5,d}n=4n=4k=3n=2k=2
Obinna Okechukwu