In general, the maximum independent set problem cannot be approximated to a constant factor in polynomial time (unless P = NP).
Általában a maximális elemszámú független halmaz problémája nem approximálható konstans faktor erejéig sem polinomiális időben (kivéve, ha P = NP).