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

<blockquote>
  <p>Pierluigi Crescenzi and LucaTrevisan:<br>
  "Max NP-completeness made easy"<br>
  Theoretical Computer Science 28, (1999), Pages 65-79</p>
</blockquote>

CC BY-SA 4.0
2018-11-20T15:14:38.580Z
2018-11-20T15:14:38.580Z
Gamow
<p>Suppose we are given a formula <span class="math-container">$\phi$</span> of 3-SAT, with variables <span class="math-container">$x_1,\dots, x_n$</span> and clauses <span class="math-container">$C_1,\dots, C_m$</span>. Consider the graph <span class="math-container">$G_\phi$</span> where there is one node for each clause <span class="math-container">$C_i$</span>, for each positive literal <span class="math-container">$x_i$</span> and for each negative literal <span class="math-container">$\overline{x_i}$</span>. A literal is adjacent to a clause if and only if this clause contains the literal. <span class="math-container">$\phi$</span> is a <em>planar instance</em> If <span class="math-container">$G_\phi$</span> is planar.</p>

<p><strong>Max planar 3-SAT</strong> is defined as the restriction of Max 3-SAT to planar instances.</p>

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

<reference-request><complexity-classes><approximation-algorithms><approximation-hardness><planar-graphs>
Does Max Planar 3-SAT admit a PTAS?
Mathieu Mari
# Does Max Planar 3-SAT admit a PTAS?

(Asked by: username_0 on 2018-11-20)

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 ?

**Tags:** reference-request, complexity-classes, approximation-algorithms, approximation-hardness, planar-graphs


---

## 1 answers

### Answer by username_1 on 2018-11-20. Score: 11 | Accepted answer

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


---

