Complexidade de encontrar o número máximo de conjuntos disjuntos em pares
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 < rPPrrnnn<rn<r
Problema A. Existem ( ) conjuntos distintos dentro dos conjuntos (ou seja, sua interseção em pares está vazia)?1 ≤ M ≤ P PMM1≤M≤P1≤M≤PPP
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 nkkk<nk<nLL1≤L≤P1≤L≤PkkPPkknn
Observação : Estou interessado principalmente no caso em que é fixo ( ).n ≥ 2 , k ≥ 2k,nk,nn≥2,k≥2n≥2,k≥2
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 nnnrrrrnn
No problema de correspondência do hipergrafo uniforme partite NP-completo?rnnrr
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 rkknnkknnrr
Exemplo ( ):n=3,r=5,P=3n=3,r=5,P=3
B = { 2 , 3 , 4 } C = { 3 , 4 , 5 }A={1,2,3}A={1,2,3} , ,B={2,3,4}B={2,3,4}C={3,4,5}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=3k=n=3M=1M=1AABBCC(A,B)(A,B)(A,C)(A,C)(B,C)(B,C)
Se , temos conjuntos distintos: uma solução é , (subconjuntos de e ).L = 2 { 1 , 2 } { 3 , 4 } A Bk=2k=2L=2L=2{1,2}{1,2}{3,4}{3,4}AABB
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=2n=1n=1n≥3n≥3
Em vez de fazer a pergunta,
Existem conjuntos disjuntos entre os conjuntos ?PMMPP
Vamos fazer a seguinte pergunta
Qual é o número máximo de conjuntos disjuntos que podemos obter dos conjuntos ?PP
É 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.MMMMM
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 )MMO(logM)O(log⁡M)
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.MM
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=n−1k=n−1
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 conjuntosTTttTTTTSi∈TSi∈T|Si|<t|Si|<t(t−|Si|)(t−|Si|)SiSiTTSi∈TSi∈Ttem 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 .AATT
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.TTnnddTT
Qual é o número máximo de conjuntos disjuntos que podemos obter retirando elementos de cada conjunto?nn
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.MMTTMM(M−1)(M−1)P=NPP=NP
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+1n=3,P=3n=3,P=3n−1=2n−1=2{1,d},{2,3},{4,5}{1,d},{2,3},{4,5}
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}A′={1,2,3,d},B′={2,3,4,d}C'={3,4,5,d}C′={3,4,5,d}n=4n=4n=4n=4k=3k=3n=2n=2k=2k=2