4
$\begingroup$

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.

$\endgroup$
9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Would a subexponential algorithm for PLANAR SAT (the SAT graph is planar) be of interest? $\endgroup$ – joro Mar 21 '15 at 13:17
  • $\begingroup$ 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. $\endgroup$ – Andy Drucker Mar 21 '15 at 19:13
  • $\begingroup$ Similarly for SAT instances whose clause/variable incidence graphs are planar. $\endgroup$ – Andy Drucker Mar 21 '15 at 19:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.