Editing Independent set (graph theory) (section)

==== In bounded degree graphs ====
In bounded degree graphs, effective approximation algorithms are known with [[approximation ratio]]s that are constant for a fixed value of the maximum degree; for instance, a [[greedy algorithm]] that forms a maximal independent set by, at each step, choosing the minimum degree vertex in the graph and removing its neighbors, achieves an approximation ratio of (Δ+2)/3 on graphs with maximum degree&nbsp;Δ.<ref>{{harvtxt|Halldórsson|Radhakrishnan|1997}}.</ref> Approximation hardness bounds for such instances were proven in {{harvtxt|Berman|Karpinski|1999}}. Indeed, even Max Independent Set on 3-regular 3-edge-colorable graphs is [[APX|APX-complete]].<ref name=chlebik>{{cite book|last1=Chlebík|first1=Miroslav|last2=Chlebíková|first2=Janka |chapter=Approximation Hardness for Small Occurrence Instances of NP-Hard Problems |author2-link=Janka Chlebíková|title=Proceedings of the 5th International Conference on Algorithms and Complexity|series=Lecture Notes in Computer Science |date=2003 |volume=2653 |pages=152–164 |doi=10.1007/3-540-44849-7_21|isbn=978-3-540-40176-6|chapter-url=https://researchportal.port.ac.uk/portal/en/publications/approximation-hardness-for-small-occurrence-instances-of-nphard-problems(fe0d8e3c-740b-4b84-9962-4a0b05cc6f6b).html}}</ref>