Ultimate greedy approximation of independent sets in subcubic graphs

Piotr Krysta, Mathieu Mari, Nan Zhi

We study the approximability of the maximum size independent set (MIS) problem in bounded degree graphs. This is one of the most classic and widely studied NP-hard optimization pro…