Irgendwelche Ergebnisse auf binärem booleschen CSP jenseits der Traktierbarkeit fester Parameter von fast 2SAT-Problemen?

12

Sei eine 2CNF-Formel und k eine nichtnegative ganze Zahl. Es ist in diesem Aufsatz bewiesen , dass das Problem der Entscheidung, ob höchstens k- Klauseln gelöscht werden können , um φ zufriedenstellend zu machen , mit festen Parametern bewerkstelligt werden kann, wobei k der Parameter ist. Meine Frage ist, ob es einige Arbeiten gibt, die dieses Ergebnis auf andere binäre boolesche CSP verallgemeinern? (Das heißt, um zu entscheiden, ob höchstens k Bedingungen gelöscht werden können , um eine CSP-Instanz erfüllbar zu machen, parametrisiert durch k ) Oder irgendwelche negativen Ergebnisse?φkkφkkk

Regelmäßigkeit
quelle
Ich bin wirklich neugierig, was ich hier vermisse - ist nicht fast 2SAT trivial fest parametrierbar, weil es für festes k nur polynomiell viele Mengen von höchstens Klauseln gibt ? kk
Dave
@Nehmen Sie an, es gibt ungefähr Klauselmengen , aber die Tractability mit festen Parametern erlaubt es k nicht, im exponentiellen Teil der Laufzeit zu erscheinen. Ö(nk)k
Regelmäßigkeit

Antworten:

8

Die Klassifizierung dieser CSP-Variante ist meines Wissens weit offen. Sie können einige Probleme mit festen Parametern in der Einstellung ausdrücken (z. B. ist d-Hitting Set ungefähr der Fall, wenn Sie positive Klauseln mit höchstens d plus negative Zuweisungen haben; ungefähr bedeutet dies, dass das CSP-Problem etwas allgemeiner ist, sich aber leicht verringert zurück zu d-HS oder mindestens gewichtetes d-HS). Selbst für Einschränkungen, die Sie über existenziell quantifizierte 2-CNF-Formeln implementieren können, ist die Komplexität offen. Das Problem ist, dass Sie beim Implementieren von Einschränkungen auf diese Weise, obwohl es sich um 2-CNF handelt, nur eine bezahlen, um das Ganze zu löschen. Daher können auch einfache Bedingungen, die nur die Verbindung von zwei anderen sind, schwierig sein (ich kann später ein Beispiel + Verweis haben).

Stefan Kratsch
quelle