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

1 Answer 1

11
$\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