4
$\begingroup$

The question Complexity of Independent Set on Triangle-Free Planar Cubic Graphs asks for the complexity of the independent set problem in triangle-free planar cubic graphs. In the statement of the question Independent set on cubic triangle-free graphs, it is claimed that a more general problem - maximum independent set in triangle-free cubic graphs (not necessarily planar) - is NP-complete. Could you please provide a reference to the paper for that result?

(Note that the answer to the first of the mentioned questions provides a paper where MIS is shown to be NP-hard in triangle-free planar graphs with vertices of degree <= 3, and I am asking for 3-regular graphs.)

Update: There has appeared a new answer in there since, and it addresses this question as well. The note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The paper "The Vertex-Disjoint Triangles Problem" (http://link.springer.com/chapter/10.1007/10692760_3) by Guruswami et al. has the proof of its NP-completeness as Theorem 3.

Update: As stated in a more recent answer to Complexity of Independent Set on Triangle-Free Planar Cubic Graphs, there is a note "NP-complete problems on a 3-connected cubic planar graph and their applications" by Ryuhei Uehara that contains a proof that MIS is NP-complete for cubic, planar, and 3-connected graphs of girth greater than 3.

Improve this answer
$\endgroup$

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.