¿Se conocen algoritmos subexponenciales para SAT PLANAR?

Algunos problemas NP-hard que son exponenciales en gráficos generales son subexponenciales en gráficos planos porque el ancho del árbol es como máximo y son exponenciales en el ancho del árbol. $4.9 \sqrt{|V(G)|}$

Básicamente, estoy interesado si hay algoritmos subexponenciales para SAT PLANAR que es NP-complete.

Sea una fórmula CNF en las variables y la cláusula -ésima es . $\phi$ $x_i$ $i$ $c_i$

El gráfico de incidencia p. 5 de está en vértices y bordes iff o . $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á en SAT PLANAR si el gráfico de incidencia es plano.

¿Existen algoritmos subexponenciales para SAT PLANAR en términos de ? $\phi$

No excluyo la posibilidad de reducir SAT a SAT PLANAR para que esto sea posible, aunque SAT todavía es exponencial y es subexponencial debido al aumento en el tamaño. $\phi$

graph-theory sat reductions joro
fuente

Hay una condición adicional en la definición de SAT PLANAR, las variables deben estar conectadas con un ciclo a través de ellas. Lo que ha descrito se conoce como PLANAR * SAT.

domotorp

@domotorp Creo que cité correctamente y el artículo afirma que el gráfico es bipartito. Tal vez en otros documentos se use el mismo nombre para otra cosa.

joro

Bueno, puede aplicar el teorema del separador plano junto con la programación dinámica y obtener el tiempo de ejecución , donde es el número de vértices en el gráfico. ¿Asumo que quieres algo mejor?

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

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

n

$n$

Sariel Har-Peled

@ SarielHar-Peled La suya será una respuesta, no necesita algo mejor (aunque mejor es bienvenido). Me molesta que diferentes fórmulas puedan tener el mismo gráfico: negar un literal.

joro

La reducción estándar de SAT a SAT planar muestra que bajo la hipótesis del tiempo exponencial, es imposible, por lo que el algoritmo del comentario de Sariel es óptimo hasta las constantes en el exponente. (esto es para lo que domotorp llama PLANAR * SAT sin embargo, pero estoy bastante seguro de que el límite inferior también se puede mostrar para PLANAT SAT)

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

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

daniello

Respuestas:

Bueno, puede aplicar el teorema del separador plano junto con la programación dinámica y obtener el tiempo de ejecución , donde es el número de vértices en el gráfico. La idea es que intente todas las asignaciones posibles para los vértices variables en el separador, y todas las variables mencionadas en las cláusulas del separador (suponiendo que cada cláusula tenga un número constante de variables). $2^{O(\sqrt{n})}$ $n$

Si un nodo de cláusula es grande, entonces debe ser un poco más inteligente: debe adivinar si debe asignarse al subproblema del lado izquierdo o del lado derecho. Los detalles de tales cosas tienden a ser confusos y no inmediatos, por lo que no voy a dar más detalles. Creo que los documentos originales de Lipton y Tarjan resolvieron problemas similares usando ideas similares, si mi memoria me sirve.

Sariel Har-Peled
fuente

En términos más generales, es bien sabido que si el gráfico de incidencia de un formulado SAT tiene un ancho de árbol como máximo entonces se puede verificar la satisfacción en el tiempo . Se garantiza que los gráficos planos con vértices tienen un ancho de árbol debido al teorema del separador plano. Más generalmente gráficos que excluyen cualquier gráfico fijo tiene un menor tener treewidth donde la constante depende del tamaño de .

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$

Chandra Chekuri

De hecho, si la fórmula tiene variables y cláusulas entonces el ancho del árbol es como máximo (en oposición al límite más crudo ). El límite superior deduce del hecho de que las variables son una cubierta de vértice del gráfico de incidencia, y los gráficos planos con una cubierta de vértice de tamaño tienen un ancho de árbol .

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})$

daniello

Este también es el ejercicio 41 de Algoritmos exactos de Woeginger de 2003 para problemas NP-Hard: una encuesta . dx.doi.org/10.1007/3-540-36478-1_17

András Salamon