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

Gegeben eine Sammlung von nicht leeren Teilmengen von $\{1,2,\ldots,N\}$ ($N$nicht 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?

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

Lassen Sie uns die Problemeinstellung leicht als zweiteiliges Diagramm umformulieren $G$mit $\{1,2,\ldots,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 $i \in X$ und $J \in Y$ iff $i \in J$. Für jeden Satz von Eckpunkten$W$ 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 $W \subseteq Y$ so dass $|N(W)| \leq |W|$. Wenn wir jedoch das Kriterium leicht auf ändern$|N(W)| \lt |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.

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.