Aufzählung aller Set-Cover, wenn mindestens ein Set bekannt ist

Question

Ich habe einen Index, der als Schlüssel Werte aus der Potenzmenge $P(S)$ einer Menge $S$ annimmt, mit Ausnahme von $\emptyset$ und $S$.

Dann habe ich eine Abfrage $Q=(s, k)$, wobei $s \in P(S) - \{\emptyset \cup S\}$ und $ 1 < k \le |S|$.

Das Ergebnis der Abfrage ist die Menge der Abdeckungen $R$ von $S$;$ forall r in r, | r | le k $.

Wenn also zum Beispiel $S = \{a, b, c, d\}$ und $Q=( \{a,b\}, 3 )$, sollte $R$ alle Cover von $S$ zurückgeben, die durch gebildet werden $\{a, b\}$ und $k = (3 - 1 = ) 2$ oder weniger andere Teilmengen von $P(S) - \{\emptyset \cup S\}$, nämlich:$ R = {$ $$ {a, b }, {c }, {d } $$ $$ {a, b }, {c, d } $$ $$ {a, b }, {a, c, d } $$ $$ {a, b }, {b, c, d } $$ $ } $

Ich möchte wissen, ob es einen effizienten Algorithmus gibt, der mir alle diese Deckungskombinationen liefern kann.

Mit anderen Worten, ich möchte wissen, ob es einen effizienten Weg gibt, alle Überdeckungen zu erhalten, die aus höchstens $k$-Elementen bestehen, wobei ich nur 1 von k Elementen kenne.

Answer 1

Der erste Schritt besteht darin, die bekannte Menge $s$ zu eliminieren.Die Idee besteht darin, alle Überdeckungen von $S \setminus s$ unter Verwendung von höchstens $k-1$ Mengen zu finden und dann die Lösung zu erweitern, indem alle Teilmengen von $s$ zu allen Mengen in einer gegebenen Überdeckung auf alle möglichen Arten hinzugefügt werden.Details weggelassen.

Für das neue Problem reicht es aus, alle Überdeckungen von $S$ der Größe genau $k$ zu finden, die weder $S$ noch $\emptyset$ verwenden.Tatsächlich können wir diese Einschränkungen ignorieren und die (relativ) wenigen Lösungen, die diese Mengen verwenden, einfach weglassen.Wir werden sie geordnet erzeugen, was einen Effizienzfaktor von $k!$ mit sich bringt;Ich bin mir sicher, dass das vermieden werden kann, aber die Details überlasse ich Ihnen.Betrachten Sie die Sets $ s_1, ldots, s_k $ in Ordnung und nehmen Sie an, dass sie $ a_1, ldots, a_k $ "neue" Elemente abdecken, das ist $ | S_1 | = a_1 $, $ | s_2 setminus s_1 | = a_2 $ und so weiter.Dann ist $a_1 + \cdots + a_k = |S|$, und wir können alle solchen Folgen (einschließlich Nullen) aufzählen.Für jede Sequenz können wir die neuen Elemente selbst aufzählen.Abschließend zählen wir alle möglichen Möglichkeiten auf, „alte“ Elemente zu Mengen hinzuzufügen. Beispielsweise könnte $S_3$ zusätzlich zu $a_3$ neue Elemente eine beliebige Teilmenge von $S_1 \cup S_2$ enthalten.