Czy znane są algorytmy podwykładnicze dla PLANAR SAT?

Niektóre problemy trudne NP, które są wykładnicze na grafach ogólnych, są sub wykładnicze na grafach płaskich, ponieważ szerokość wynosi co najwyżej i są wykładnicze w szerokości. $4.9 \sqrt{|V(G)|}$

Zasadniczo jestem zainteresowany, czy istnieją algorytmy podwykładnicze dla PLANAR SAT, który jest NP-zupełny.

Niech być wzór nanowłókien węglowych o zmiennych i -tym klauzula . $\phi$ $x_i$ $i$ $c_i$

Wykres występowania s. 5 z jest na wierzchołkach i na krawędziach iff lub . $G$ $\phi$ $V(G)=\{x_i\} \cup \{c_i\}$ $(x_i,c_i)$ $x_i \in c_i$ $\lnot x_i \in c_i$

jest w PLANARZE SAT, jeśli wykres występowania jest płaski. $\phi$

Czy istnieją algorytmy podwykładnicze dla PLANAR SAT pod względem ? $\phi$

Nie wykluczam możliwości zredukowania SAT do PLANARU SAT, aby było to możliwe, chociaż SAT wciąż ma charakter wykładniczy, a jest subeksponcyjny z powodu wzrostu wielkości. $\phi$

graph-theory sat reductions joro
źródło

Istnieje dodatkowy warunek w definicji PLANARU SAT, zmienne muszą być połączone z cyklem przez nie. To, co opisałeś, jest znane jako PLANAR * SAT.

domotorp

@domotorp Myślę, że cytowałem poprawnie, a papier twierdzi, że wykres jest dwustronny. Może w innych artykułach ta sama nazwa jest używana do czegoś innego.

joro

Możesz zastosować twierdzenie o separatorze planarnym wraz z programowaniem dynamicznym i uzyskać czas działania

, gdzie

jest liczbą wierzchołków na wykresie. Zakładam, że chcesz czegoś lepszego?

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

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

n

$n$

Sariel Har-Peled

@ SarielHar-Peled Twój będzie odpowiedzią, nie potrzebujesz czegoś lepszego (chociaż lepiej jest mile widziany). Błędy mi różne formuły mogą mieć ten sam wykres - zanegować literał.

joro

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

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

Odpowiedzi:

Możesz zastosować twierdzenie o separatorze planarnym wraz z programowaniem dynamicznym i uzyskać czas działania 2 O ( $2^{O(\sqrt{n})}$ $n$

Jeśli węzeł klauzuli jest duży, musisz być nieco bardziej sprytny - musisz zgadnąć, czy przypisać go do podproblemu po lewej czy po prawej stronie. Szczegóły takich rzeczy bywają nieporządne i nie są natychmiastowe, więc nie zamierzam podawać więcej szczegółów. Myślę, że oryginalne prace Liptona i Tarjana rozwiązały podobne problemy przy użyciu podobnych pomysłów, jeśli moja pamięć dobrze mi służy.

Sariel Har-Peled
źródło

k

$k$

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

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

n

$n$

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

n

$n$

m

$m$

O (\sqrt{n})

$O(\sqrt{n})$

O (\sqrt{n + m})

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

O (\sqrt{n})

$O(\sqrt{n})$

n

$n$

O (\sqrt{n})

$O(\sqrt{n})$

Jest to także ćwiczenie 41 z Dokładnych algorytmów Woegingera z 2003 r. Dla trudnych problemów NP: ankieta . dx.doi.org/10.1007/3-540-36478-1_17

András Salamon