Existem algoritmos subexponenciais para o PLANAR SAT conhecidos?

Alguns problemas difíceis de NP que são exponenciais em gráficos gerais são subexponenciais em gráficos planares porque a largura da árvore é no máximo e eles são exponenciais na largura da árvore. $4.9 \sqrt{|V(G)|}$

Basicamente, estou interessado se existem algoritmos subexponenciais para o PLANAR SAT, que é NP-completo.

Seja uma fórmula CNF nas variáveis e a ésima cláusula é . $\phi$ $x_i$ $i$ $c_i$

O gráfico de incidência p. 5 de está nos vértices e arestas se ou . $G$ $\phi$ $V(G)=\{x_i\} \cup \{c_i\}$ $(x_i,c_i)$ $x_i \in c_i$ $\lnot x_i \in c_i$

$\phi$ está em PLANAR SAT se o gráfico de incidência for plano.

Existem algoritmos subexponenciais para o PLANAR SAT em termos de ? $\phi$

Não excluo a possibilidade de reduzir SAT para PLANAR SAT para tornar isso possível, embora SAT ainda seja exponencial e seja subexponencial por causa do aumento no tamanho. $\phi$

graph-theory sat reductions joro
fonte

Existe uma condição extra na definição de PLANAR SAT, as variáveis devem ser conectadas com um ciclo através delas. O que você descreveu é conhecido como PLANAR * SAT.

domotorp

@domotorp Acho que citei corretamente e o artigo afirma que o gráfico é bipartido. Talvez em outros trabalhos o mesmo nome seja usado para outra coisa.

Joro

Bem, você pode aplicar o teorema do separador planar junto com a programação dinâmica e obter o tempo de execução , em que é o número de vértices no gráfico. Eu suponho que você quer algo melhor?

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

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

n

$n$

Sariel Har-Peled

@ SarielHar-Peled O seu será uma resposta, não precisa de algo melhor (embora melhor seja bem-vindo). Bugs me diferentes fórmulas podem ter o mesmo gráfico - negar um literal.

Joro

A redução padrão de SAT para SAT planar mostra que, sob a hipótese de tempo exponencial, é impossível, portanto o algoritmo do comentário de Sariel é ideal até constantes no expoente. (isto é para que domotorp chama PLANAR * SAT embora, mas eu tenho certeza que o limite pode ser mostrado para PLANAT SAT muito inferior)

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

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

Daniello

Respostas:

Bem, você pode aplicar o teorema do separador planar junto com a programação dinâmica e obter o tempo de execução , em que é o número de vértices no gráfico. A ideia é que você tente todas as atribuições possíveis para os vértices de variáveis no separador e todas as variáveis mencionadas nas cláusulas no separador (supondo que cada cláusula tenha um número constante de variáveis). $2^{O(\sqrt{n})}$ $n$

Se um nó de cláusula é grande, você precisa ser um pouco mais inteligente - você precisa adivinhar se deve atribuí-lo ao subproblema do lado esquerdo ou direito. Os detalhes de tais coisas tendem a ser confusos e não imediatos, por isso não vou dar mais detalhes. Acho que os artigos originais de Lipton e Tarjan resolveram problemas semelhantes usando idéias semelhantes, se minha memória me servir bem.

Sariel Har-Peled
fonte

Mais genericamente, é bem conhecido que, se o gráfico de incidência de um sab formulat tem treewidth no máximo

, em seguida, pode-se verificar satisfazibilidade em

tempo. Gráficos planares com

vértices têm garantia de largura de árvore

k

$k$

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

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

n

$n$

devido ao teorema do separador planar. Geralmente, os gráficos que excluem qualquer gráfico fixo

têm uma menor largura de árvore

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

, onde a constante depende do tamanho de

O (\sqrt{n})

$O(\sqrt{n})$

H

$H$

Chandra Chekuri

De fato, se a fórmula tem

variáveis e cláusulas

, a largura da árvore é no máximo

n

$n$

m

$m$

(como oposto à mais bruto

O (\sqrt{n})

$O(\sqrt{n})$

ligado). O

O (\sqrt{n + m})

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

o limite superior segue o fato de que as variáveis são uma cobertura de vértice do gráfico de incidência e gráficos planares com uma cobertura de vértice de tamanho

têm largura de árvore

O (\sqrt{n})

$O(\sqrt{n})$

n

$n$

O (\sqrt{n})

$O(\sqrt{n})$

Daniello 27/03

Este também é o exercício 41 dos algoritmos exatos de Woeginger para 2003, para problemas difíceis com NP: uma pesquisa . dx.doi.org/10.1007/3-540-36478-1_17

András Salamon