Was ist die folgende Variante von Set Cover?

15

Was ist die folgende Variation von Set Cover?

Wenn eine Menge S, eine Sammlung C von Teilmengen von S und eine positive ganze Zahl K gegeben sind, gibt es K Mengen in C, so dass jedes Paar von Elementen von S in einer der ausgewählten Teilmengen liegt.

Hinweis: Es ist nicht schwer zu erkennen, dass dieses Problem NP-vollständig ist: Erstellen Sie bei einem normalen Deckblattproblem (S, C, K) drei Kopien von S, sagen Sie S ', S' 'und S' ''. dann erstelle deine Teilmengen als S '' ', | S | Teilmengen der Form {a '} U {x in S' '| x! = a} U {a '' '}, | S | Teilmengen der Form {a ''} U {x in S '| x! = a} U {a '' '}, {a', a '' | a in C_i}. Dann können wir das Set-Cover-Problem mit K Teilmengen lösen, wenn wir das Pair-Cover-Problem mit K + 1 + 2 | S | lösen können Teilmengen.

Dies verallgemeinert sich auf Dreifache usw. Ich würde gerne nicht eine halbe Seite verschwenden, um dies zu beweisen, und es ist wahrscheinlich nicht offensichtlich genug, dies als trivial abzutun. Es ist sicherlich ausreichend nützlich, dass jemand es bewiesen hat, aber ich habe keine Ahnung, wer oder wo.

Gibt es auch einen guten Ort, um nach NP-Vollständigkeitsergebnissen zu suchen, die nicht in Garey und Johnson vorliegen?

deinst
quelle

Antworten:

7

Um Ihre zweite Frage zu beantworten, ist das Kahn-Crescenzi-Kompendium der NP-Härteergebnisse eine wertvolle Quelle für Härteergebnisse und deckt auch viele Varianten der Kernprobleme von G & J ab. Der Eintrag für Set Cover ist ein gutes Beispiel dafür.

Suresh Venkat
quelle
2
Ich hatte das schon einmal gesehen und ja, es hilft, aber es kratzt nicht einmal an der Oberfläche von dem, was sich als NP-Complete erwiesen hat. Um ein weiteres Beispiel zu nennen: Ich habe viel länger gebraucht, um Ueharas Beweis zu finden, dass Vertex Cover NP-vollständig ist, als ich gebraucht habe, um es zu beweisen. (Ihr Beweis war viel sauberer als meiner.)
Deinst
7

Es hört sich so an, als würden Sie die Mengenabdeckung verallgemeinern, um nicht nur Elemente von S, sondern jede Untergruppe von S der Größe M zu berücksichtigen. Wir können das Problem allgemeiner formulieren:

Was ist bei gegebener Menge S, einer Sammlung C von Teilmengen von S und einer positiven ganzen Zahl m die kleinste Anzahl von Elementen von C, so dass jede Teilmenge der Größe M von S in einem der ausgewählten Elemente von C liegt?

Dies scheint mir eine ziemlich offensichtliche Verallgemeinerung der Deckung zu sein, und keine, die Sie brauchen, um die NP-Vollständigkeit jenseits einer einzigen Zeile zu beweisen. Wenn Sie schließlich m = 1 wählen, wird das ursprüngliche Problem mit der Satzabdeckung behoben. Vielleicht ist diese allgemeinere Formulierung gut genug für Ihre Zwecke, um nicht auf die Details eingehen zu müssen?


Ihre Frage zu einem aktualisierten Satz von NP-Vollständigkeitsergebnissen ist gut und verdient eine eigene Frage. Crescenzi und Kann haben hier ein nützliches Kompendium online zusammengestellt .

Zweitens ist es kaum allgegenwärtig, aber das Algorithmen Design Manual von Steven Skiena ist oft ein nützlicher erster Anschlag für eine große Anzahl von Problemen und ist im Online - Teil .

Anand Kulkarni
quelle
Ich interessiere mich nur für m = 2. Es kann sein, dass es einen einzeiligen Beweis gibt, aber dieser Beweis entgeht mir. Ich glaube, das habe ich im zweiten Satz der Frage klar gesagt.
Deinst
Entschuldigung; Ich wollte nicht vorschlagen, dass es im paarweisen Fall einen kurzen Beweis gibt! Der von mir vorgeschlagene einzeilige Beweis ist nur in der allgemeinen Version des Problems: "Der Sonderfall von m = 1 stellt die Standardsatzabdeckung wieder her". Wie Sie hervorheben, ist der Beweis im paarweisen Fall offensichtlich (fügen Sie Dummy-Elemente und Sets zum Standard-Set-Cover hinzu, um ein paar-Set-Cover zu generieren), aber ja, es würde ein paar Zeilen dauern, um zu zeigen, dass es formal ist. Ich werde sehen, ob ich Hinweise darauf in der Literatur finden kann.
Anand Kulkarni