1
$\begingroup$

As we all know, 3-SAT is NP-hard. Two of the less known results are that Planar 3-SAT is NP-hard and also a 'restricted' 3-SAT, where any literal appears in at most two clauses turns out to be NP-hard. My question is if there is any known result on what happens if we combine these two conditions? That is, suppose we are given an instance of Planar 3-SAT problem, but with additional constraint that each of the literals appears at most twice. Can we solve this problem in poly time?

My intuition tells me it should be NP hard, since in Planar 3-SAT instance at most 2 literals are contained in at least 3 clauses, as otherwise we would get an induced $K_{3,3}$ in the bipartite graph of clauses and variables (right?).

Edit: Since it has come to my attention that not everybody can open the first link, for the relevant definition of Planar 3-SAT problem, please consult the Wikipedia page

Improve this question
$\endgroup$
4
  • $\begingroup$ Your first link is not freely accessible. Perhaps it would help to define what is Planar 3-SAT. $\endgroup$
    – Nathaniel
    Commented Jan 30, 2023 at 14:23
  • $\begingroup$ That's strange, since I can access it even in the incognito mode. Anyway, it links to Lichtensteins paper that proves NP-completeness, in case someone else has issues opening the link and I will add the link to Wikipedia page as well. Thanks for letting me know! :) $\endgroup$
    – Freshman's Dream
    Commented Jan 30, 2023 at 14:35
  • $\begingroup$ Incognito mode doesn't hide your university's IP address. $\endgroup$
    – John K.
    Commented Jan 30, 2023 at 18:20
  • $\begingroup$ Do you understand the proof of NP-hardness for the restricted 3-SAT? Have you tried applying that reduction to Planar 3-SAT? What do you get? Does the resulting instance, after applying that reduction, remain planar? $\endgroup$
    – D.W. ♦
    Commented Jan 30, 2023 at 18:42

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.