3
$\begingroup$

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.

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

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)

Improve this answer
$\endgroup$
1
$\begingroup$

Actually, there is a simple gadget to remove vertices of degree larger than three. See, e.g., the answer here. Note that this gadget keeps planarity.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Saeed
    Apr 23, 2020 at 6:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.