Komplexität beim Finden der maximalen Anzahl paarweiser disjunkter Mengen

Angenommen, ich habe Mengen mit Elementen aus r möglichen. Jeder Satz hat die Größe n ( n < r ), wobei sich die Sätze überlappen können. Ich möchte feststellen, ob die folgenden zwei Probleme NP-vollständig sind oder nicht:$P$$r$$n$$n<r$

Problem A. Gibt es ( 1 ≤ M ≤ P ) verschiedene Mengen innerhalb der P- Mengen (dh ihr paarweiser Schnittpunkt ist leer)?$M$$1 \le M \le P$$P$

Aufgabe B. Nun können aus jeder Menge ( k < n ) Elemente ausgewählt werden. Gibt es innerhalb der P- Sätze jeweils L ( 1 ≤ L ≤ P ) unterschiedliche Mengen der Größe k ? Es ist zu beachten, dass nur ein Satz von k Elementen aus jedem Satz von n Elementen entnommen werden kann .$k$$k<n$$L$$1 \le L \le P$$k$$P$$k$$n$

Bemerkung : Ich interessiere mich hauptsächlich für den Fall, dass fest sind ( n ≥ 2 , k ≥ 2 ).$k,n$$n \ge 2, k \ge 2$

Ich denke, dass Problem A als Einheit gedacht werden kann$n$ partitiges Hypergraph-Matching-Problem angesehen werden kann. Das heißt, wir haben die Elemente von r als Eckpunkte, und jede Hyperkante enthält eine Teilmenge von n Eckpunkten des Graphen.$r$$r$$n$

1. In dem uniformen r- partiten Hypergraphen-Matching-Problem NP-vollständig?$n$$r$

2. Ich denke, dass Problem B gleichbedeutend ist mit dem Ermitteln der Anzahl unterschiedlicher Hyperkanten der Kardinalität die aus Hyperkanten der Kardinalität n entnommen wurden . Ist diese eingeschränkte Version (in dem Sinne, dass jede k- Kardinalitätsmenge aus einer vorgewählten Menge von n Elementen und nicht willkürlich aus r Elementen entnommen wird ) von Problem A NP-vollständig?$k$$n$$k$$n$$r$

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

Wenn , gibt es nur M = 1 eine bestimmte Menge, die A oder B oder C ist , da jedes der Paare ( A , B ) , ( A , C ) ,$k=n=3$$M=1$$A$$B$$C$$(A,B)$$(A,C)$ nicht hat leere Kreuzung.$(B,C)$

Wenn , haben wir L = 2 verschiedene Mengen: Eine Lösung ist { 1 , 2 } , { 3 , 4 } (Teilmengen von $k=2$$L=2$$\{1,2\}$$\{3,4\}$$A$ und ).$B$

Dies ist ein Sonderfall des Maximum-Set-Packing-Problems, und sowohl Problem A als auch Problem B sind NP-vollständig . Beachten Sie, dass das Problem einfach ein Übereinstimmungsproblem ist, wenn und auch einfach ist, wenn n = 1 ist . Also gehe ich von n ≥ 3 aus .$n=2$$n=1$$n \ge 3$

Anstatt die Frage zu stellen,

Gibt es disjunkte Mengen unter den P Mengen?$M$$P$

Stellen wir die folgende Frage

Was ist die maximale Anzahl von disjunkten Mengen, die wir aus den Mengen erhalten können?$P$

Es ist klar, dass, wenn die zweite Frage in Polynomzeit beantwortet werden kann, dies auch die erste ist, da wir diesen Maximalwert nur mit und JA ausgeben müssen, wenn $M$$M$ kleiner oder gleich diesem Maximum ist, und ansonsten NEIN .

Wenn die erste Frage in Polynomzeit beantwortet werden kann, ist dies auch die zweite, da wir die binäre Suche für und die Antwort auf die zweite Frage erhalten und nur einen Faktor von O ( log M ) hinzufügen können.$M$$O(\log{M})$

Daraus können wir schließen, dass beide Fragen gleichwertig sind. dh Frage 1 ist genau dann polylomial lösbar, wenn Frage 2 dies auch ist.

Es ist auch klar, dass die Probleme in NP liegen, da wir leicht überprüfen können, ob die ausgegebenen Sätze disjunkt sind.$M$

Die Frage ist nun, wie wir ein bekanntes NP-Hard-Problem auf dieses reduzieren können. Um dies zu erreichen, reduzieren wir das maximal eingestellte Verpackungsproblem . Ich werde mich einfach auf Problem A konzentrieren, da Problem B leicht als schwierig gezeigt werden kann, indem $k=n-1$

Betrachten Sie eine beliebige Instanz der maximalen Satz Packungsproblem . Beachten Sie, dass der einzige Unterschied zwischen Problem A und dem ursprünglichen Problem der maximalen Satzverpackung darin besteht, dass in Problem A die Größe der Sätze gleich sein muss. Lassen t die maximale Mächtigkeit unter allen Sätzen in seiner T . Wenn jeder Satz in T die gleiche Mächtigkeit haben, sind wir fertig und die eingestellte Abdeckung Problem ist exactlly Problem A. Nun , da nehme an, für einige Satz S i ∈ T , haben wir | S i | < t . Wir fügen einfach ( t - | S i | ) Elemente hinzu$T$$t$$T$$T$$S_i \in T$$|S_i| < t$$(t-|S_i|)$ die keine Elemente einer Menge in T sind . Wir wiederholen diesen Vorgang, bis alle Mengen S i ∈ T die gleiche Größe haben. Es ist klar, dass das Hinzufügen neuer Elemente auf diese Weise die Größe der maximalen Anzahl disjunkter Mengen nicht ändert.$S_i$$T$$S_i \in T$

Wenn wir also Problem in Polynomzeit lösen können, können wir das maximale Packungsproblem in Polynomzeit lösen, da wir nur die zusätzlichen Elemente entfernen müssen, die wir hinzugefügt haben, und dies ändert nichts an der Größe der maximale Anzahl disjunkter Mengen in T .$A$$T$

BEARBEITEN - Einige zusätzliche Informationen zu Problem B.

Angenommen, Problem B hat eine Polynomzeitlösung, betrachten Sie nun eine beliebige Instanz von Problem A mit n Elementen pro Menge. Nun fügen wir jedem Satz in T ein Dummy-Element d hinzu . Wir stellen nun die folgende Frage.$T$$n$$d$$T$

Was ist die maximale Anzahl disjunkter Mengen, die wir erhalten können, wenn wir Elemente aus jeder Menge nehmen?$n$

Jetzt wissen wir, dass unter den Mengen im Maximum höchstens eine das Dummy-Element enthalten kann. Wenn also die Antwort, die wir als Maximum erhalten, , dann ist die tatsächliche maximale Anzahl von Mengen in Instanz T (unser ursprüngliches Problem A). ist entweder M oder ( $M$$T$$M$ , dies ergibt jedoch eine konstante Faktornäherung für die maximale eingestellte Packung. Undsolche Annäherung ist nur möglichwenn P = N P . Problem B ist also auch schwer.$(M-1)$$P=NP$