<p>You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; such algorithms exist for many graph problems). If you could get $|V(G)| = o(m^2)$ in the reduction you mention, this would imply that the Exponential Time Hypothesis (ETH) is false. This is well-appreciated, yet it has not led to any improvements on running times for CNF-SAT (as far as I know).  For more on how ETH has been used to classify the difficulty of planar (and non-planar) graph problems, see e.g. <a href="http://www.win.tue.nl/~nikhil/courses/2013/2WO08/eth-lowerbounds.pdf">this survey</a> of Lokshtanov, Marx, and Saurabh.</p>

<p>As for reducing the constant in such reductions, achieving $|V(G)| = c m^2$ for $c$ as small as possible, I don't know how much effort has been devoted to this.</p>

CC BY-SA 3.0
2015-03-21T13:17:59.837Z
Would a subexponential algorithm for PLANAR SAT (the SAT graph is planar) be of interest?
joro
CC BY-SA 3.0
2015-03-21T19:13:49.870Z
I don't know exactly which problem you mean, but e.g. for 2-CSPs with planar underlying graph on $n$ vertices, $2^{O(\sqrt{n})}$ runtime is possible by known techniques (that you mention) and $2^{o(\sqrt{n})}$ would falsify ETH.
Andy Drucker
CC BY-SA 3.0
2015-03-21T19:20:06.900Z
Similarly for SAT instances whose clause/variable incidence graphs are planar.
Andy Drucker
CC BY-SA 3.0
2015-03-21T12:19:38.853Z
2015-03-21T12:19:38.853Z
Andy Drucker
<p>Let $\phi$ be CNF formula with $n$ variables and $m$ clauses.</p>

<p>I am looking for a reduction is $\phi$ satisfiable to a problem
on a planar graph $G$ with as few vertices as possible.</p>

<p>The majority of reductions I have seen use "crossing gadget",
which replaces edge crossing by a planar graph.</p>

<p>So far the best reference is $|V(G)|=m^2$.</p>

<p>The motivation is that the treewidth of planar graphs
is at most $4.9 \sqrt{|V(G)|}$ and this gives subexponential
complexity for problems exponential in the treewidth like
Independent Set.</p>

<graph-theory><sat><reductions>
Reduction SAT to a problem on a planar graph with as few vertices as possible
joro
# Reduction SAT to a problem on a planar graph with as few vertices as possible

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

Let $\phi$ be CNF formula with $n$ variables and $m$ clauses.

I am looking for a reduction is $\phi$ satisfiable to a problem
on a planar graph $G$ with as few vertices as possible.

The majority of reductions I have seen use "crossing gadget",
which replaces edge crossing by a planar graph.

So far the best reference is $|V(G)|=m^2$.

The motivation is that the treewidth of planar graphs
is at most $4.9 \sqrt{|V(G)|}$ and this gives subexponential
complexity for problems exponential in the treewidth like
Independent Set.

**Tags:** graph-theory, sat, reductions

---

## 1 answers

### Answer by username_1 on 2015-03-21. Score: 9

You are right that improved reductions from CNF-SAT to any one of various planar graph problems would give improved algorithms for CNF-SAT (via graph algorithms with runtimes exponential in treewidth; such algorithms exist for many graph problems). If you could get $|V(G)| = o(m^2)$ in the reduction you mention, this would imply that the Exponential Time Hypothesis (ETH) is false. This is well-appreciated, yet it has not led to any improvements on running times for CNF-SAT (as far as I know). For more on how ETH has been used to classify the difficulty of planar (and non-planar) graph problems, see e.g. [this survey](http://www.win.tue.nl/~nikhil/courses/2013/2WO08/eth-lowerbounds.pdf) of Lokshtanov, Marx, and Saurabh.

As for reducing the constant in such reductions, achieving $|V(G)| = c m^2$ for $c$ as small as possible, I don't know how much effort has been devoted to this.

> **Comments:**
> **username_0**: Would a subexponential algorithm for PLANAR SAT (the SAT graph is planar) be of interest?  
> **username_1**: I don't know exactly which problem you mean, but e.g. for 2-CSPs with planar underlying graph on $n$ vertices, $2^{O(\sqrt{n})}$ runtime is possible by known techniques (that you mention) and $2^{o(\sqrt{n})}$ would falsify ETH.  
> **username_1**: Similarly for SAT instances whose clause/variable incidence graphs are planar.  

---

