patternMinor
MIS complexity in cubic triangle-free graphs
Viewed 0 times
cubicfreegraphstrianglecomplexitymis
Problem
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.
(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.
Solution
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.
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.
Context
StackExchange Computer Science Q#52926, answer score: 3
Revisions (0)
No revisions yet.