Finden Sie eine kleine Obermenge von mindestens k von n gegebenen Mengen

7

Sagen wir, wir sind gegeben n Sätze und die Größe ihrer Vereinigung ist m. Wir möchten eine kleine Menge konstruieren, die mindestens enthältk des n gegebene Sätze.

Nehmen wir das an m ist weniger als ein Polynom in ndh: m<P(n). In diesem Fall gibt es einen effizienten (Polynom-) Algorithmus für das Optimierungsproblem:

Finden Sie den kleinsten Satz, der mindestens enthält k des n gegebene Sätze.

Ezeidman
quelle
Haben Sie eine Beziehung zwischen n und m? Ich meine, ist es richtig anzunehmen, dass n <= m ist?
Die dominierende Menge für zweigeteilte Graphen ist NP-Hard. Dies könnte zutreffen.
Aryabhata

Antworten:

8

Das Problem ist NP-vollständig. Hier ist eine Reduktion von 3SAT-5, einer NP-vollständigen Version von 3SAT, in der jede Variable genau fünfmal vorkommt (und daher die Anzahl der Variablen und die Anzahl der Klauseln linear zusammenhängen).

Wir beginnen mit dem Aufbau von zwei Mengen-Systemen. Das erste SystemS besteht aus 6 Sätzen A0,A1,B0,B1,C0,C1 und 15 Elemente D={0,1}4(1,1,1,1)und hat die folgende Eigenschaft:

|AiBjCk|={14if i=j=k=0,13otherwise.
Das eingestellte System ist gegeben durch
Ai={(a,b,c,d)D:a=i},Bi={(a,b,c,d)D:b=i},Ci={(a,b,c,d)D:c=i}.
Die einzigen Elemente, die nicht von abgedeckt werden AiBjCk sind die der Form (1i,1j,1k,d). Wenni=j=k=0 dann gibt es ein solches Element, sonst gibt es zwei.

Das zweite System T besteht aus 2n setzt X1,Y1,,Xn,Yn und O(n2)Elemente und hat die folgende Eigenschaft. Rufen Sie eine Familie vonn setzt aus T richtig, wenn es genau eines von jedem enthältXi,Yi. Alle richtigen Familien vonn Sets decken die gleiche Anzahl von Elementen ab Mund jede unangemessene Familie von n Sets deckt mindestens ab M+1 Elemente.

Die Menge der Elemente besteht aus allen ungeordneten Paaren von Mengen {S,T} andere als die der Form {Xi,Yi}. Jedes SetST besteht aus allen 2n2Paare, die es enthalten. LassenF eine Familie von sein n Sets, mit Ergänzung F¯. Die einzigen Elemente, die nicht von abgedeckt werdenF sind die der Form {S,T} wo S,TF¯. WennF ist dann richtig so ist F¯und so gibt es Elemente, die nicht behandelt werden. Wenn korrekt ist, gilt dies auch für , sodass weniger als Elemente nicht behandelt werden.(n2)FF¯(n2)

Die Reduzierung. Sei eine Instanz von 3SAT-5 mit Variablen und Klauseln. Für jede Klausel gibt es eine Kopie von system . Es gibt auch eine Kopie von in der jedes Element durch Elemente ersetzt wird. Die Gesamtzahl der Elemente ist in polynomisch .ϕnm=5n/3ϕjSjST~TN=13m+1n

Für jede Variable gibt es zwei Mengen und . Die Menge ist die Vereinigung der folgenden sechs Mengen:xiXi0Xi1Xi0

  • die Menge vonXiT~
  • Wenn für jede Klausel die an der ersten Position enthält, positiv erscheint, dann die Menge von , andernfalls die Menge vonϕjxixiA0SjA1Sj
  • für jede Klausel die an der zweiten Position enthält, entweder oder (wie oben)ϕjxiB0B1
  • für jede Klausel die an der dritten Position enthält, entweder oder (wie oben)ϕjxiC0C1

Die Menge ist ähnlich definiert als die Vereinigung der folgenden sechs Mengen:Xi1

  • die Menge vonYiT~
  • Wenn für jede Klausel die an der ersten Position enthält, negativ erscheint, dann die Menge von , andernfalls die Menge vonϕjxixiA0SjA1Sj
  • für jede Klausel die an der zweiten Position enthält, entweder oder (wie oben)ϕjxiB0B1
  • für jede Klausel die an der dritten Position enthält, entweder oder (wie oben)ϕjxiC0C1

Das Problem besteht darin, zu entscheiden, ob es Mengen gibt, die zusammen Elemente (oder weniger) abdecken .n13m+NM

Wenn erfüllt werden kann, sagen wir mit der Wahrheitszuweisung , dann deckt genau Elemente ab. Nehmen wir umgekehrt an, es gibt eine Möglichkeit, höchstens Elemente abzudecken . Wenn die Lösung nicht korrekt ist, deckt sie mindestens Elemente ab (wobei nur berücksichtigt wird ). Wenn es richtig ist, entspricht es einer Wahrheitszuweisung , und es ist leicht zu überprüfen, ob die Anzahl der abgedeckten Elemente beträgt , wobei die Anzahl der gefälschten Klauseln ist. Daher ist und wir schließen daraus, dassϕxi{Xixi:1in}13m+NM13m+NMN(M+1)>13m+NMT~xi13m+NM+ZZZ=0xi ist eine befriedigende Aufgabe.

Yuval Filmus
quelle