Complexité de la recherche du nombre maximal d'ensembles disjoints par paire

Supposons que j'ai des ensembles avec des éléments pris parmi les r possibles. Chaque ensemble est de taille n ( n < r ), où les ensembles peuvent se chevaucher. Je veux déterminer si les deux problèmes suivants sont NP-complets ou non:$P$$r$$n$$n<r$

Problème A. Y a-t-il ( 1 ≤ M ≤ P ) ensembles distincts dans les ensembles P (c'est-à-dire que leur intersection par paire est vide)?$M$$1 \le M \le P$$P$

Problème B. Maintenant, ( k < n ) éléments peuvent être choisis dans chaque ensemble. Y a-t-il L ( 1 ≤ L ≤ P ) ensembles distincts de taille k chacun dans les P ensembles? Notez qu'un seul ensemble de k éléments peut être pris dans chaque ensemble de n éléments.$k$$k<n$$L$$1 \le L \le P$$k$$P$$k$$n$

Remarque : je m'intéresse principalement au cas où sont fixes ( n ≥ 2 , k ≥ 2 ).$k,n$$n \ge 2, k \ge 2$

Je pense que le problème A peut être considéré comme un problème de correspondance d'hyper-graphes r -partite uniforme . Autrement dit, nous avons les éléments de r comme sommets, et chaque hyper-bord contient un sous-ensemble de n sommets du graphique.$n$$r$$r$$n$

1. Dans le problème d' appariement d'hyper-graphes r -partite uniforme NP-complet?$n$$r$

2. Je pense que le problème B équivaut à trouver le nombre d'hyper-bords distincts de cardinalité pris à partir d'hyper-bords de cardinalité n . Est-ce que cette version restreinte (dans le sens où chaque ensemble de k- cardinalité est tirée d'un ensemble présélectionné de n éléments plutôt que prise arbitrairement de r éléments) du problème A NP-complète?$k$$n$$k$$n$$r$

Exemple ( ):$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\}$

Si , il n'y a que M = 1 un ensemble distinct, qui est A ou B ou C , puisque chacune des paires ( A , B ) , ( A , C ) , ( B , C ) a intersection vide.$k=n=3$$M=1$$A$$B$$C$$(A,B)$$(A,C)$$(B,C)$

Si , nous avons L = 2 ensembles distincts: une solution est { 1 , 2 } , { 3 , 4 } (sous-ensembles de A et B ).$k=2$$L=2$$\{1,2\}$$\{3,4\}$$A$$B$

Il s'agit d'un cas spécial du problème d'emballage maximal défini et les problèmes A et B sont tous deux NP-Complete . Notez que le problème est simplement un problème d'appariement si et est également facile si n = 1 . Je vais donc supposer n ≥ 3 .$n=2$$n=1$$n \ge 3$

Au lieu de poser la question,

Y a-t-il ensembles disjoints parmi les ensembles P ?$M$$P$

Posons la question suivante

Quel est le nombre maximum d'ensembles disjoints que nous pouvons obtenir des ensembles ?$P$

$M$$M$

$M$$O(\log{M})$

Nous pouvons donc conclure que les deux questions sont équivalentes. c'est-à-dire que la question 1 est résolue en temps polylomial si et seulement si la question 2 l'est aussi.

$M$

$k=n-1$

$T$$t$$T$$T$$S_i \in T$$|S_i| < t$$(t-|S_i|)$$S_i$$T$$S_i \in T$

$A$$T$

EDIT - Quelques informations supplémentaires sur le problème B

$T$$n$$d$$T$

$n$

$M$$T$$M$$(M-1)$$P=NP$