MAXIMUM INDEPENDENT SET problem

MAXIMUM INDEPENDENT SET problem --- задача о нахождении наибольшего независимого множества.

The MAXIMUM INDEPENDENT SET problem (or MISP) consists in finding an independent set of the largest cardinality. This problem is known to be NP-hard, approximable within factor [math]\displaystyle{ {\mathcal O}(|V|/(\log |V|)^{2}) }[/math], and not approximable within factor [math]\displaystyle{ |V|^{1-\epsilon} }[/math] for any [math]\displaystyle{ \epsilon \gt 0 }[/math].