Existe-t-il des algorithmes sous-exponentiels pour PLANAR SAT?

Certains problèmes NP-durs qui sont exponentiels sur les graphes généraux sont sous-exponentiels sur les graphes planaires car la largeur de l'arborescence est au maximum de et ils sont exponentiels dans la largeur de l'arborescence. $4.9 \sqrt{|V(G)|}$

Fondamentalement, je suis intéressé s'il existe des algorithmes sous-exponentiels pour PLANAR SAT qui est NP-complet.

Soit une formule CNF sur les variables et la -ième clause est . $\phi$ $x_i$ $i$ $c_i$

Le graphique d'incidence p. 5 de est sur les sommets et les arêtes si 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 en PLANAR SAT si le graphique d'incidence est planaire.

Existe-t-il des algorithmes sous-exponentiels pour PLANAR SAT en termes de $\phi$ ?

Je n'exclus pas la possibilité de réduire SAT en PLANAR SAT pour rendre cela possible, bien que SAT soit toujours exponentiel et soit sous-exponentiel en raison de l'augmentation de la taille. $\phi$

graph-theory sat reductions joro
la source

Il y a une condition supplémentaire dans la définition de PLANAR SAT, les variables doivent être connectées avec un cycle à travers elles. Ce que vous avez décrit est appelé PLANAR * SAT.

domotorp

@domotorp Je pense avoir cité correctement et le papier prétend que le graphique est bipartite. Peut-être que dans d'autres journaux, le même nom est utilisé pour autre chose.

joro

Eh bien, vous pouvez appliquer le théorème du séparateur planaire avec la programmation dynamique et obtenir le temps d'exécution

, où

est le nombre de sommets du graphe. Je suppose que tu veux quelque chose de mieux?

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

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

n

$n$

Sariel Har-Peled

@ SarielHar-Peled La vôtre sera une réponse, vous n'avez pas besoin de quelque chose de mieux (bien que mieux soit le bienvenu). Bugs me différentes formules peuvent avoir le même graphique - annuler un littéral.

joro

La réduction standard de SAT à SAT planaire montre que sous l'hypothèse de temps exponentiel,

est impossible, donc l'algorithme du commentaire de Sariel est optimal jusqu'aux constantes de l'exposant. (c'est pour ce que domotorp appelle PLANAR * SAT, mais je suis presque sûr que la limite inférieure peut également être affichée pour PLANAT SAT)

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

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

daniello

Eh bien, vous pouvez appliquer le théorème du séparateur planaire avec la programmation dynamique et obtenir le temps d'exécution , oùest le nombre de sommets du graphe. L'idée étant d'essayer toutes les affectations possibles pour les sommets de variables sur le séparateur, et toutes les variables mentionnées dans les clauses du séparateur (en supposant que chaque clause a un nombre constant de variables). $2^{O(\sqrt{n})}$ $n$

Si un nœud de clause est grand, alors vous devez être un peu plus intelligent - vous devez deviner s'il doit être affecté au sous-problème du côté gauche ou du côté droit. Les détails de telles choses ont tendance à être désordonnés et pas immédiats, donc je ne vais pas donner plus de détails. Je pense que les articles originaux de Lipton et Tarjan ont résolu des problèmes similaires en utilisant des idées similaires, si ma mémoire est bonne.

Sariel Har-Peled
la source

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

Il s'agit également de l'exercice 41 des algorithmes exacts de 2003 de Woeginger pour les problèmes NP-difficiles: une enquête . dx.doi.org/10.1007/3-540-36478-1_17

András Salamon

Existe-t-il des algorithmes sous-exponentiels pour PLANAR SAT?

Réponses: