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.)

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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