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 < $P$$r$$n$$n<r$

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

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 $k$$k<n$$L$$1 \le L \le P$$k$$P$$k$$n$

Observação : Estou interessado principalmente no caso em que é fixo ( ).n ≥ 2 , k ≥ $k,n$$n \ge 2, k \ge 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 $n$$r$$r$$n$

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

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 $k$$n$$k$$n$$r$

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=3$$M=1$$A$$B$$C$$(A,B)$$(A,C)$$(B,C)$

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

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 ≥ $n=2$$n=1$$n \ge 3$

Em vez de fazer a pergunta,

Existem conjuntos disjuntos entre os conjuntos ?$M$$P$

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.$M$$M$

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$M$$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.$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 definindo$k=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 conjuntos$T$$t$$T$$T$$S_i \in T$$|S_i| < t$$(t-|S_i|)$$S_i$$T$$S_i \in T$tem 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 .$A$$T$

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.$T$$n$$d$$T$

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.$M$$T$$M$$(M-1)$$P=NP$