Ist das Finden der kleinsten Sammlung von Teilmengen so, dass die Anzahl der Elemente unter den Teilmengen <= die Anzahl der Teilmengen NP-hart ist?

7

Gegeben eine Sammlung von nicht leeren Teilmengen von {1,2,,N} (Nnicht behoben) besteht das Problem darin, die kleinste nicht leere Sammlung von Teilmengen zu finden, so dass die Anzahl der unterschiedlichen Elemente, die in der Vereinigung von Teilmengen auftreten, kleiner oder gleich der Anzahl der ausgewählten Teilmengen ist. Dies scheint ein NP-hartes Problem zu sein, aber ich kann es nicht beweisen. Irgendeine Hilfe?

user2566092
quelle
1
Was hast du versucht? Wo bist du festgefahren? Was ist Ihre Begründung dafür, dass dies NP-hart ist?
ZeroUltimax
@ZeroUltimax Ich habe über Dinge wie Set-Cover nachgedacht, aber das würde bedeuten, die minimale Anzahl von Strings zu finden, damit alle Zeichen erscheinen. Ich habe auch versucht, eine Beziehung zu einem Cliquenproblem zu finden, bin aber auch dort festgefahren. Der Grund, warum ich glaube, dass dies NP-schwer ist, ist, dass ich versucht habe, polynomielle Zeitalgorithmen zu entwickeln, und fehlgeschlagen bin. Außerdem hat jemand eine ähnliche Frage auf StackOverflow gestellt und nach einem schnellen Algorithmus gefragt. Alles, was er bekam, war Brute Force und eine Reduzierung auf Ganzzahlprogrammierung.
user2566092
Es sieht so aus, als hätte diese Frage nichts mit Strings zu tun. Die Reihenfolge der Buchstaben in jeder Zeichenfolge ist irrelevant, daher können Sie dies als Frage zu Mengen behandeln. Ich schlage vor, Sie bearbeiten die Frage entsprechend. Was hast du versucht? Haben Sie versucht, eine Liste von NP-vollständigen Problemen zu betrachten, die Sätze von Sätzen betreffen?
DW
@ DW Ich habe die Frage so geändert, dass sie sich auf Sets gemäß Ihrem Vorschlag bezieht. Ja, ich habe mir Fragen zu Sets und Cliquen angesehen, bin aber festgefahren. Es sieht so aus, als hätte jemand eine Lösung mit Clique. Ich überprüfe sie immer noch.
user2566092

Antworten:

2

Dies ist zu lang für einen Kommentar, aber keine vollständige Antwort.

Lassen Sie uns die Problemeinstellung leicht als zweiteiliges Diagramm umformulieren Gmit {1,2,,N}=X als eine Menge von Eckpunkten und die Sammlung von Teilmengen (sagen wir, Y) als die andere Menge von Eckpunkten mit einer Kante dazwischen iX und JY iff iJ. Für jeden Satz von EckpunktenW im Y, definieren N(W) die Nachbarschaft von sein W im G - nämlich die Menge aller Eckpunkte in X die neben mindestens einem Scheitelpunkt in liegen W.

Dann fragt das Problem nach einer minimalen Teilmenge WY so dass |N(W)||W|. Wenn wir jedoch das Kriterium leicht auf ändern|N(W)|<|W|finden wir, dass eine solche Teilmenge genau dann existiert, wenn es keine Übereinstimmung zwischen gibt X und Y das deckt Y, denn es ist genau gleichbedeutend mit Halls Hochzeitssatz .

Da solche Übereinstimmungen in Polynomzeit auffindbar sind (z. B. über Hopcroft-Karp ), denke ich, dass diese Version des Problems wahrscheinlich relativ einfach sein sollte, aber ich müsste noch etwas arbeiten, um herauszufinden, ob und wie die Standardalgorithmen für zweiteilig sind Matching legt diese mangelhaften Sätze offen und ob minimale mangelhafte Sätze auch leicht erhalten werden können oder nicht . Außerdem kann ich nicht sofort sagen, wie viel schwieriger die ursprüngliche Version des Problems ist (was erlaubt|N(W)|=|W|) ist als diese modifizierte Version.

mhum
quelle
0

Sie können von Clique reduzieren. Erstellen Sie eine Menge für jeden Scheitelpunkt mit jeweils n-1 Elementen, die den n-1 anderen Scheitelpunkten entsprechen, wobei das Element für v in Menge u gleich dem Element für u in Menge v ist (jedoch nicht gleich einem anderen Element), wenn {u, v} ist eine Kante und ansonsten ein eindeutiges Element. Dann können wir k Strings auswählen, die zusammen k (nk) + k (k-1) / 2 Elemente enthalten, wenn nur dann, wenn es eine Clique der Größe k gibt. Wir müssen dann nur die richtige Anzahl von Ein-Element-Sätzen hinzufügen, die dasselbe Element enthalten, sodass die Anzahl der ausgewählten Sätze und der gesammelten Elemente gleich ist.

Falk Hüffner
quelle
Dies funktioniert nicht: Wenn Sie einen Satz mit einem Element haben, ist die Auswahl dieses Satzes allein immer eine optimale Lösung.
FrankW
Richtig, kleinere Lösungen zu vermeiden ist ein Problem. Daran habe ich nicht gedacht.
Falk Hüffner