On the Maximum Independent Set Problem in Graphs of Bounded Maximum Degree
Ngoc C. Lê
,
Trung Tran
We consider the maximum independent set (MIS) problem, i.e., the problem asking for a vertex subset of maximum cardinality of a graph such that no two vertices in this set are adjacent. The problem is known to be NP-hard in general, even if restricted on graphs of maximum degree at most