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

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.

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".

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$\mathcal{C}$$r$$S$$k$
$k$
$\mathcal{C'} \subseteq \mathcal{C}$$k$

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)

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) \in E(G)\}$

$u$$v$

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]$$\Delta = 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.