6
$\begingroup$

Suppose we are given a formula $\phi$ of 3-SAT, with variables $x_1,\dots, x_n$ and clauses $C_1,\dots, C_m$. Consider the graph $G_\phi$ where there is one node for each clause $C_i$, for each positive literal $x_i$ and for each negative literal $\overline{x_i}$. A literal is adjacent to a clause if and only if this clause contains the literal. $\phi$ is a planar instance If $G_\phi$ is planar.

Max planar 3-SAT is defined as the restriction of Max 3-SAT to planar instances.

This problem is known to be NP-hard. Is this problem also APX-Hard or there exists a known PTAS for this problem ?

$\endgroup$
10
$\begingroup$

Yes, a PTAS for Max-Planar-3-SAT can be constructed by using Brenda Baker's approach.
This has been observed, for instance, in Theorem 17 in

Pierluigi Crescenzi and LucaTrevisan:
"Max NP-completeness made easy"
Theoretical Computer Science 28, (1999), Pages 65-79

$\endgroup$

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.