Cheap and Secure Web Hosting Provider : See Now

MIS complexity in cubic triangle-free graphs

, , No Comments
Problem Detail: 

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

Asked By : Yury Kartynnik
Answered By : Yury Kartynnik

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/52926

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback