Gibt es subexponentielle Algorithmen für PLANAR SAT?

Einige NP-harte Probleme, die in allgemeinen Graphen exponentiell sind, sind in ebenen Graphen subexponentiell, da die Baumbreite höchstens beträgt $4.9 \sqrt{|V(G)|}$ und sie sind exponentiell in der Baumbreite.

Grundsätzlich interessiert mich, ob es subexponentielle Algorithmen für PLANAR SAT gibt, die NP-vollständig sind.

Sei $\phi$ eine CNF-Formel für Variablen $x_i$ und der $i$ te Satz ist $c_i$ .

Das Inzidenzdiagramm p. 5 $G$ von $\phi$ liegt auf Eckpunkten $V(G)=\{x_i\} \cup \{c_i\}$ und Kanten $(x_i,c_i)$ wenn $x_i \in c_i$ oder $\lnot x_i \in c_i$ .

$\phi$ ist in PLANAR SAT, wenn der Inzidenzgraph planar ist.

Gibt es subexponentielle Algorithmen für PLANAR SAT in Bezug auf $\phi$ ?

Ich schließe die Möglichkeit nicht aus, SAT auf PLANAR SAT zu reduzieren, um dies zu ermöglichen, obwohl SAT immer noch exponentiell ist und aufgrund der Zunahme der Größe subexponentiell ist. $\phi$

graph-theory sat reductions joro
quelle

Es gibt eine zusätzliche Bedingung in der Definition von PLANAR SAT, die Variablen müssen mit einem Zyklus verbunden werden. Was Sie beschrieben haben, ist als PLANAR * SAT bekannt.

Domotorp

@domotorp Ich glaube, ich habe richtig zitiert und das Papier behauptet, das Diagramm sei zweiteilig. Vielleicht wird in anderen Zeitungen derselbe Name für etwas anderes verwendet.

Joro

Nun, Sie können den Satz des planaren Separators zusammen mit der dynamischen Programmierung anwenden und die Laufzeit

, wobei

die Anzahl der Eckpunkte im Diagramm ist. Ich nehme an, du willst etwas besseres?

2^{O (\sqrt{n})}

$2^{O( \sqrt{n})}$

n

$n$

Sariel Har-Peled

@ SarielHar-Peled Dein wird eine Antwort sein, brauche nichts besseres (obwohl besser ist willkommen). Bugs mir verschiedene Formeln können das gleiche Diagramm haben - negieren Sie ein Literal.

Joro

Die Standardreduktion von SAT zu planarem SAT zeigt, dass unter der Exponentialzeithypothese

ist unmöglich, daher ist der Algorithmus von Sariels Kommentar bis zu Konstanten im Exponenten optimal. (Dies ist für das, was Domotorp PLANAR * SAT nennt, aber ich bin mir ziemlich sicher, dass die Untergrenze auch für PLANAT SAT angezeigt werden kann)

2^{o (\sqrt{n})}

$2^{o(\sqrt{n})}$

daniello

Antworten:

Nun, Sie können den Satz des planaren Separators zusammen mit der dynamischen Programmierung anwenden und die Laufzeit , wobeidie Anzahl der Eckpunkte im Diagramm ist. Die Idee ist, dass Sie alle möglichen Zuweisungen für die Variablenscheitelpunkte auf dem Separator und alle Variablen, die in Klauseln im Separator erwähnt werden, versuchen (vorausgesetzt, jede Klausel hat eine konstante Anzahl von Variablen). $2^{O(\sqrt{n})}$ $n$

Wenn ein Klauselknoten groß ist, muss man ein bisschen schlauer sein - man muss raten, ob man ihn dem linken oder rechten Teilproblem zuordnet. Die Details für solche Dinge sind in der Regel chaotisch und nicht unmittelbar, daher werde ich keine weiteren Details angeben. Ich denke, die Originalarbeiten von Lipton und Tarjan haben ähnliche Probleme mit ähnlichen Ideen gelöst, wenn mein Gedächtnis mir recht tut.

Sariel Har-Peled
quelle

Ganz allgemein ist es bekannt , dass , wenn der Einfall Graph eines SAT formulat Baumweite höchstens hat

dann kann man in Erfüllbarkeit überprüft

Zeit. Planare Graphen mit

Ecken haben garantiert die Baumbreite

k

$k$

2^{O (k)} p o l y (| ϕ |)

$2^{O(k)} poly(|\phi|)$

n

$n$

aufgrund des Satzes vom planaren Separator. Im Allgemeinen haben Graphen, die einen festen Graphen

eine geringe Baumbreite

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

wobei die Konstante von der Größe von

abhängt.

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

Chandra Chekuri

Wenn die Formel

Variablen und

Klauseln enthält, ist die Baumbreite höchstens

n

$n$

m

$m$

(im Gegensatz zum roheren

O (\sqrt{n})

$O(\sqrt{n})$

gebunden). Das

O (\sqrt{n + m})

$O(\sqrt{n+m})$

obere Schranke ergibt sich aus der Tatsache, dass die Variablen eine Scheitelpunktabdeckung des Inzidenzgraphen sind und planare Graphen mit einer Scheitelpunktabdeckung der Größe

eine Baumbreite

O (\sqrt{n})

$O(\sqrt{n})$

n

$n$

O (\sqrt{n})

$O(\sqrt{n})$

Danielo

Dies ist auch Aufgabe 41 von Woegingers Exakten Algorithmen für NP- schwierige Probleme von 2003: Eine Umfrage . dx.doi.org/10.1007/3-540-36478-1_17

András Salamon