5
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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