<p>A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.</p>

<blockquote>
  <p>Bojan Mohar:<br>
  "Face Covers and the Genus Problem for Apex Graphs"<br>
  Journal of Combinatorial Theory, Series B 82, 102-117 (2001)</p>
</blockquote>

CC BY-SA 4.0
2020-04-14T21:02:06.237Z
2020-04-14T21:02:06.237Z
Gamow
<p>Actually, there is a simple gadget to remove vertices of degree larger than three. See, e.g., <a href="https://cs.stackexchange.com/questions/43173/prove-vertex-cover-of-maximum-degree-3-is-npc">the answer here</a>. Note that this gadget keeps planarity.</p>

CC BY-SA 4.0
2020-04-23T06:47:39.000Z
Mohar did similar to this (see the other answer to this post), by now it is a standard technique, back then I have no idea.
Saeed
CC BY-SA 4.0
2020-04-22T14:16:42.163Z
2020-04-22T14:16:42.163Z
Yixin Cao
<p>In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation from vertex cover and for vertex cover (I suppose in cubic planar graphs) they cite the paper of Garey, Johnson and Stockmeyer 1976.</p>

<p>When I looked at their DBLP entry, there is a single paper that matches the description of the mentioned paper:</p>

<p><a href="https://doi.org/10.1016/0304-3975(76)90059-1" rel="nofollow noreferrer">Some Simplified NP-complete Graph Problems.</a></p>

<p>Having checked the paper, the reduction for vertex cover in graphs of maximum degree 3 is for general graphs, not planar graphs. For planar graphs, they only have a reduction that shows hardness on planar graphs of maximum degree 6, not 3 (already the gadget has vertices of degree 6).</p>

<p>I'm wondering if I'm missing something here since there are consequent papers building upon the aforementioned comment of the book.</p>

<graph-theory><np-complete><planar-graphs><independent-set><vertex-cover>
Is the maximum independent set in cubic planar graphs NP-complete?
Saeed
# Is the maximum independent set in cubic planar graphs NP-complete?

(Asked by: username_0 on 2020-04-14)

In their famous book, Garey and Johnson, write a comment that the maximum independent set problem, in cubic planar graphs is NP-complete(page 194 of the book). They say this is by a transformation from vertex cover and for vertex cover (I suppose in cubic planar graphs) they cite the paper of Garey, Johnson and Stockmeyer 1976.

When I looked at their DBLP entry, there is a single paper that matches the description of the mentioned paper:

[Some Simplified NP-complete Graph Problems.](https://doi.org/10.1016/0304-3975(76)90059-1)

Having checked the paper, the reduction for vertex cover in graphs of maximum degree 3 is for general graphs, not planar graphs. For planar graphs, they only have a reduction that shows hardness on planar graphs of maximum degree 6, not 3 (already the gadget has vertices of degree 6).

I'm wondering if I'm missing something here since there are consequent papers building upon the aforementioned comment of the book.

**Tags:** graph-theory, np-complete, planar-graphs, independent-set, vertex-cover

---

## 2 answers

### Answer by username_1 on 2020-04-14. Score: 10 | Accepted answer

A complete NP-completeness proof for this problem is given right after Theorem 4.1 in the following paper.

> Bojan Mohar:  
> "Face Covers and the Genus Problem for Apex Graphs"  
> Journal of Combinatorial Theory, Series B 82, 102-117 (2001)


---

### Answer by username_2 on 2020-04-22. Score: 1

Actually, there is a simple gadget to remove vertices of degree larger than three. See, e.g., [the answer here](https://cs.stackexchange.com/questions/43173/prove-vertex-cover-of-maximum-degree-3-is-npc). Note that this gadget keeps planarity.

> **Comments:**
> **username_0**: Mohar did similar to this (see the other answer to this post), by now it is a standard technique, back then I have no idea.  

---

