Does anyone know whether the maximum independent set problem is NP-hard in triangle free d-regular graphs and if it's NP-hard for all d larger than some threshold t? Can anyone provide a reference also?
1
-
1$\begingroup$ The intuition would be that you have NP-hardness already for d=3. see e.g. sciencedirect.com/science/article/pii/S0012365X10001974 which goes about similar questions $\endgroup$– Dima PasechnikCommented Nov 6, 2017 at 8:03
Add a comment
|