4
$\begingroup$

The classic reduction from 3SAT to PLANAR-3SAT requires a removal of $O(m^2)$ crossings from a rectilinear representation of 3SAT with $m$ clauses. However, the crossing number inequality suggests that it may not be necessary to have that many crossings.

Is there a way to reduce 3SAT to PLANAR-3SAT in time $O(m^{2-\varepsilon})$ with $\varepsilon>0$ (or less) for subclasses of 3SAT (e.g., read-(at most)-$r$ 3SAT with bounded $r$)?

Improve this question
$\endgroup$
6
  • 4
    $\begingroup$ I believe such a reduction would refute ETH, using fast exptime algorithms for planar-3sat. (If we are defining planar-3sat in terms of the "clause-clause" graph.) $\endgroup$
    – Ryan Williams
    Commented Feb 4, 2018 at 4:45
  • $\begingroup$ @RyanWilliams Indeed. I know refuting ETH is a tall order, but the bipartite graphs related to 3SAT have limitations in their degree sequences, especially if appearance of variables is restricted. The crossing number lemma leaves room for subclasses of these graphs to have a crossing number in $o(m^2)$. I now restrict the question to subclasses of 3SAT, as this is slightly more likely. $\endgroup$
    – delete000
    Commented Feb 4, 2018 at 17:45
  • 1
    $\begingroup$ For SAT instances with $O(n)$ clauses the "sufficuently many edges compared to vertices" of the crossing number inequality does not hold. For instances with a superlinear number of clauses, applying the sparsification lemma and then then the standard reduction does the job. $\endgroup$
    – daniello
    Commented Feb 4, 2018 at 21:11
  • $\begingroup$ @daniello For 3SAT instances with $n$ variables and $m$ clauses, if we fix $\alpha=m/n=4$, then we have that the number of edges is $e=3m=3 \alpha n = 12n$, which fulfills the requirement $e>4n$ for the crossing number lemma to hold. Am I missing something? $\endgroup$
    – delete000
    Commented Feb 4, 2018 at 23:00
  • 2
    $\begingroup$ The part about the crossing number inequality in my previous comment is nonsense. In fact the crossing number inequality is in the wrong direction to have any bearing on this question - it lower bounds the number of crossings, and the bound is not tight for graphs with a linear number of edges. Indeed, 3-regular expanders need $\Omega(n^2)$ crossings. $\endgroup$
    – daniello
    Commented Feb 5, 2018 at 3:52

0

Reset to default

Your Answer

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