Finding independent set in a cubic graph

80 Views Asked by At

This question is a reference request. I am pretty sure that finding an independent set of size at least $k$ in $G$, where $G$ is a cubic graph, is an NP-hard problem. However, I did not find any source where the result is proven. Please share with the source information if you know where it is proven.

1

There are 1 best solutions below

0
On BEST ANSWER

Maximum independent sets in 3- and 4-regular Hamiltonian graphs by Fleischner, Sabidussi, and Sarvanov proves more: that the independent set problem is NP-complete for $3$-regular Hamiltonian planar graphs. (It follows that it's NP-complete for $3$-regular graphs in general, since the same reduction works if we forget that its result is Hamiltonian and planar.)

This is not the first $3$-regular graph proof. The authors write:

That MIS is an NP-complete problem for $3$-regular Hamiltonian graphs is probably a well-known piece of graph-theoretic folklore. Not having found any reference in the literature, we include here a proof, at the same time strengthening the result...

Also, they cite Gary and Johnson's Computers and Intractability (p. 194) for the result when the graphs are $3$-regular and planar but not Hamiltonian.