<p>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). </p>

<p>If a clause node is large, then you have to be a bit more clever - you have to guess whether to assign it to the left side or right side subproblem. The details for such things tends to be messy and not immediate, so I am not going to give more details. I think the original papers by Lipton and Tarjan solved similar problems using similar ideas, if my memory serves me right.</p>

CC BY-SA 3.0
2015-03-26T23:47:02.863Z
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$.
Chandra Chekuri
CC BY-SA 3.0
2015-03-27T23:07:29.420Z
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})$.
daniello
CC BY-SA 3.0
2015-11-02T13:11:00.010Z
This is also exercise 41 of Woeginger's 2003 _Exact Algorithms for NP-Hard Problems: A Survey_.  http://dx.doi.org/10.1007/3-540-36478-1_17
András Salamon
CC BY-SA 3.0
2015-03-26T19:51:49.843Z
2015-03-26T19:51:49.843Z
Sariel Har-Peled
<p>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.</p>

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

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

<p>The <a href="https://dspace.library.uvic.ca:8443/bitstream/handle/1828/4137/Churchley_Ross_MSc_2012.pdf?sequence=3&amp;isAllowed=y">incidence graph p. 5</a>
$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$.</p>

<p>$\phi$ is in PLANAR SAT if the incidence graph is planar.</p>

<blockquote>
  <p>Are there subexponential algorithms for PLANAR SAT in terms of $\phi$?</p>
</blockquote>

<p>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.</p>

CC BY-SA 3.0
2015-03-21T21:43:24.157Z
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.
domotorp
CC BY-SA 3.0
2015-03-22T13:25:24.830Z
@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
CC BY-SA 3.0
2015-03-22T18:26:01.963Z
Yes, in many papers the definition is bad, but my one is the correct :) I mean this is how it was originally defined, see definition at beginning of Section 3: http://general-k-cut.googlecode.com/svn/trunk/articles/planar_formulate_and_their_uses(d.lichtenstein).pdf
domotorp
CC BY-SA 3.0
2015-03-23T04:35:22.783Z
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?
Sariel Har-Peled
CC BY-SA 3.0
2015-03-23T05:30:28.620Z
@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
CC BY-SA 3.0
2015-03-24T22:31:25.017Z
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)
daniello
<graph-theory><sat><reductions>
Are there subexponential algorithms for PLANAR SAT known?
joro
# Are there subexponential algorithms for PLANAR SAT known?

(Asked by: username_0 on 2015-03-21)

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](https://dspace.library.uvic.ca:8443/bitstream/handle/1828/4137/Churchley_Ross_MSc_2012.pdf?sequence=3&isAllowed=y)
$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.

**Tags:** graph-theory, sat, reductions
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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.  
> **username_1**: Yes, in many papers the definition is bad, but my one is the correct :) I mean this is how it was originally defined, see definition at beginning of Section 3: http://general-k-cut.googlecode.com/svn/trunk/articles/planar_formulate_and_their_uses(d.lichtenstein).pdf  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_3**: 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)  

---

## 1 answers

### Answer by username_2 on 2015-03-26. Score: 14 | Accepted answer

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).

If a clause node is large, then you have to be a bit more clever - you have to guess whether to assign it to the left side or right side subproblem. The details for such things tends to be messy and not immediate, so I am not going to give more details. I think the original papers by Lipton and Tarjan solved similar problems using similar ideas, if my memory serves me right.

> **Comments:**
> **username_4**: 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$.  
> **username_3**: 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})$.  
> **username_5**: This is also exercise 41 of Woeginger's 2003 _Exact Algorithms for NP-Hard Problems: A Survey_.  http://dx.doi.org/10.1007/3-540-36478-1_17  

---

