Ist das Problem der parametrisierten maximalen unabhängigen Klauseln in FPT ein Problem?

8

Problem mit parametrisierten maximalen unabhängigen Klauseln:
Eingabe: Eine r-CNFSAT-Formel F mit n Variablen und m Klauseln, k
Fragen: Gibt es mindestens k Klauseln, so dass sie voneinander unabhängig sind, dh keine Variable kommt mehr als einmal in allen diesen Klauseln zusammen vor.
Parameter: k
Ich möchte wissen, ob dieses Problem in FPT liegt oder nicht. In beiden Situationen wird eine Idee, weiterzumachen, geschätzt.

Gaurav
quelle
1
Sind das k in "k-CNF" und das k in der Frage dieselbe Variable? Und was ist der Parameter dieses Problems?
Tsuyoshi Ito
Haben Sie auch versucht, Ihr Problem auf unterschiedliche Weise darzulegen, dh ohne sich auf CNF-Formeln zu beziehen? "The Hypergraph Matching" und "The R-Set Packing" (wobei r sich auf Ihr erstes k bezieht, die Anzahl der Variablen in jeder Klausel) scheinen gebräuchliche Namen für dieses Problem zu sein.
Tsuyoshi Ito
Der Parameter ist wahrscheinlich . Dies scheint mir gleichbedeutend damit zu sein, ein Maximum zu finden, das einem Hypergraphen entspricht. Ich bin mir nicht sicher, wie ich sehe, dass es sich um eine "Formel" handelt, die einen Unterschied macht (mit anderen Worten, ich sehe nicht, wie negierte Literale das Problem beeinflussen - nicht dass sie müssen, nur neugierig). k
Neeldhara
@Tsuyoshi: Eine schnelle Suche zeigt auch nichts über die parametrisierte Komplexität des Problems der maximalen Hypergraph-Übereinstimmung, sodass die Frage trotz der Neufassung interessant bleibt.
Neeldhara
@Neeldhara: Ich vermute, dass der Parameter entweder das einfache k oder das fette k ist , nicht das kursive ! k
Tsuyoshi Ito

Antworten:

5

Ich gehe davon aus, dass sich das k in k-CNF von der Anzahl der Klauseln k unterscheidet und dass letztere der Parameter ist. Ich werde k-CNF im Folgenden durch k'-CNF ersetzen.

Dieses Problem ist in FPT für jedes k '. Beachten Sie, dass in der Problemdefinition keine "Logik" verwendet wird. Sie können also einfach davon ausgehen, dass Sie eine Sammlung von m Mengen von n Elementen haben, wobei jede Menge höchstens k 'Kardinalität aufweist. (Das Entfernen der Zeichen der Literale ändert nichts am Problem.)

Jetzt fragen Sie nach einer Satzverpackung der Größe k aus einer Sammlung der Größe m, wobei jeder Satz höchstens k 'Kardinalität hat . Dies ist FPT, wenn jeder Satz eine konstante Größe hat. Es gibt viele Hinweise auf dieses Problem, der Schlüsselbegriff lautet "Set Packing".

Ryan Williams
quelle
Eigentlich dachte ich, die anderen gaben umfassendere Antworten. Nachdem ich die Antwort von Serge gesehen hatte, dachte ich darüber nach, meine zu löschen ...
Ryan Williams
11

Das Problem ist als r-Set Packing bekannt :
Instanz: Eine Sammlung von Teilmengen der Größe höchstens einer endlichen Menge und einer ganzen Zahl . Parameter: Frage: Gibt es eine Untersammlung die aus mindestens voneinander getrennten Teilmengen besteht? r S k k C 'C kCrSk
k
CCk

Für unbegrenztes ist das Problem W [1] -hart durch eine einfache Reduktion von Independent Set (siehe zum Beispiel [1]). Für die Konstante r wird das Problem jedoch mit festen Parametern nachvollziehbar (siehe zum Beispiel [2]).r
r

[1]: Rodney G. Downey, Michael R. Fellows: Parametrisierte Komplexität. Springer, 1999.
[2]: Michael R. Fellows, Christian Knauer, Naomi Nishimura, Prabhakar Ragde, Frances A. Rosamond, Ulrike Stege, Dimitrios M. Thilikos und Sue Whitesides: Schnellere feststellbare Algorithmen mit festen Parametern für Matching- und Packprobleme. Algorithmica 52 (2): 167 & ndash; 176 (2008)

Serge Gaspers
quelle
6

Lassen Sie mich versuchen, eine explizite Zwei-Wege-Reduzierung zu geben, die die FPT / W-Härte in verschiedenen Situationen deutlich machen soll (es wird dringend empfohlen, die hervorragenden Referenzen in den anderen Antworten nachzuschlagen, da dies nur etwas ist, das ich nach dem Lesen ausgearbeitet habe Ihre Frage, und ich hätte ganz leicht etwas übersehen können).

k

(i,j)i<j

{(u,v) | (u,v)E(G)}

uv

Hier ist eine Reduktion auf eine unabhängige Menge: Fügen Sie für jede Menge einen Scheitelpunkt ein und fügen Sie eine Kante zwischen zwei Mengen hinzu, wenn sie ein gemeinsames Element haben. Wiederum entspricht eine Menge von voneinander getrennten Mengen in der Familie genau einer unabhängigen Menge in diesem Diagramm.

W[1]Δ=O(1)N[v]|N[v]|

Aus diesem Grund ist Ihr Problem im Allgemeinen W-schwer und FPT im Sonderfall, wenn die Größen der Sets in der angegebenen Familie begrenzt sind.

Neeldhara
quelle
1
(u,v)
Aha - das hat funktioniert, vielen Dank! Ersparte mir eine Reise nach Meta :)
Neeldhara
1
Double-Backslash-Curly funktioniert in Mathe, denke ich.
David Eppstein
Das ist ganz richtig; und das Verhalten wird auch in den MO-FAQ erklärt: mathoverflow.net/faq Anscheinend hat es etwas mit Markdown-Interferenzen zu tun, und anscheinend ist die Verwendung von Backticks auch eine andere Lösung.
Neeldhara