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

Improve this question
$\endgroup$
6
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 at 22:31

1 Answer 1

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

Improve this answer
$\endgroup$
3
  • 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, 2015 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, 2015 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, 2015 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.