# Are there subexponential algorithms for PLANAR SAT known?

Some NP-hard problems which are exponential on general graphs are subexponential on planar graphs because the treewidth is at most $4.9 \sqrt{|V(G)|}$ and they are exponential in the treewidth.

Basically I am interested if there are subexponential algorithms for PLANAR SAT which is NP-complete.

Let $\phi$ be a CNF formula on variables $x_i$ and the $i$-th clause is $c_i$.

The incidence graph p. 5 $G$ of $\phi$ is on vertices $V(G)=\{x_i\} \cup \{c_i\}$ and edges $(x_i,c_i)$ iff $x_i \in c_i$ or $\lnot x_i \in c_i$.

$\phi$ is in PLANAR SAT if the incidence graph is planar.

Are there subexponential algorithms for PLANAR SAT in terms of $\phi$?

I don't exclude the possibility reduction SAT to PLANAR SAT to make this possible, though SAT still to be exponential and $\phi$ is subexponential because of the increase in the size.

• There is an extra condition in the definition of PLANAR SAT, the variables must be connected with a cycle through them. What you have described is known as PLANAR* SAT. Mar 21 '15 at 21:43
• @domotorp I think I cited correctly and the paper claims the graph is bipartite. Maybe in other papers the same name is used for something else.
– joro
Mar 22 '15 at 13:25
• Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O( \sqrt{n})}$, where $n$ is the number of vertices in the graph. I assume you want something better? Mar 23 '15 at 4:35
• @SarielHar-Peled Yours will be an answer, don't need something better (though better is welcome). Bugs me different formulas might have the same graph -- negate a literal.
– joro
Mar 23 '15 at 5:30
• The standard reduction from SAT to planar SAT shows that under the exponential time hypothesis, $2^{o(\sqrt{n})}$ is impossible, so the algorithm from Sariel's comment is optimal up to constants in the exponent. (this is for what domotorp calls PLANAR* SAT though, but i'm pretty sure the lower bound can be shown for PLANAT SAT too) Mar 24 '15 at 22:31

Well, you can apply the planar separator theorem together with dynamic programming and get running time $2^{O(\sqrt{n})}$, where $n$ is the number of vertices in the graph. The idea being that you try all possible assignments for the variable vertices on the separator, and all variables mentioned in clauses in the separator (assuming each clause has a constnat number of variables).
• More generally it is well-known that if the incidence graph of a SAT formulat has treewidth at most $k$ then one can check satisfiability in $2^{O(k)} poly(|\phi|)$ time. Planar graphs with $n$ vertices are guaranteed to have treewidth $O(\sqrt{n})$ due to the planar separator theorem. More generally graphs that exclude any fixed graph $H$ has a minor have treewidth $O(\sqrt{n})$ where the constant depends on size of $H$. Mar 26 '15 at 23:47
• Indeed, if the formula has $n$ variables and $m$ clauses then the treewidth is at most $O(\sqrt{n})$ (as opposed to the more crude $O(\sqrt{n+m})$ bound). The $O(\sqrt{n})$ upper bound follows from the fact hat the variables are a vertex cover of the incidence graph, and planar graphs with a vertex cover of size $n$ have treewidth $O(\sqrt{n})$. Mar 27 '15 at 23:07