26
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – domotorp Mar 21 '15 at 21:43
  • 1
    $\begingroup$ @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. $\endgroup$ – joro Mar 22 '15 at 13:25
  • 3
    $\begingroup$ 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? $\endgroup$ – Sariel Har-Peled Mar 23 '15 at 4:35
  • 2
    $\begingroup$ @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. $\endgroup$ – joro Mar 23 '15 at 5:30
  • 3
    $\begingroup$ 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) $\endgroup$ – daniello Mar 24 '15 at 22:31
14
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Chandra Chekuri Mar 26 '15 at 23:47
  • 4
    $\begingroup$ 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})$. $\endgroup$ – daniello Mar 27 '15 at 23:07
  • $\begingroup$ This is also exercise 41 of Woeginger's 2003 Exact Algorithms for NP-Hard Problems: A Survey. dx.doi.org/10.1007/3-540-36478-1_17 $\endgroup$ – András Salamon Nov 2 '15 at 13:11

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.