Editing Independent set (graph theory) (section)

=== Approximation algorithms ===
In general, the maximum independent set problem cannot be approximated to a constant factor in polynomial time (unless P = NP).  In fact, Max Independent Set in general is [[APX#Related complexity classes|Poly-APX-complete]], meaning it is as hard as any problem that can be approximated to a polynomial factor.<ref>{{cite journal|last1=Bazgan|first1=Cristina|author1-link=Cristina Bazgan|last2=Escoffier|first2=Bruno|last3=Paschos|first3=Vangelis Th.|title=Completeness in standard and differential approximation classes: Poly-(D)APX- and (D)PTAS-completeness|journal=Theoretical Computer Science|date=2005|volume=339|issue=2–3|pages=272–292|doi=10.1016/j.tcs.2005.03.007|s2cid=1418848 |url=https://basepub.dauphine.fr/handle/123456789/3724|doi-access=free}}</ref>  However, there are efficient approximation algorithms for restricted classes of graphs.

==== In planar graphs ====
In [[planar graph]]s, the maximum independent set may be approximated to within any approximation ratio ''c''&nbsp;<&nbsp;1 in polynomial time; similar [[polynomial-time approximation scheme]]s exist in any family of graphs closed under taking [[Minor (graph theory)|minors]].<ref>{{harvtxt|Baker|1994}}; {{harvtxt|Grohe|2003}}.</ref>

==== 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>

==== In interval intersection graphs ====
{{Main|Interval scheduling}}
An [[interval graph]] is a graph in which the nodes are 1-dimensional intervals (e.g. time intervals) and there is an edge between two intervals if and only if they intersect. An independent set in an interval graph is just a set of non-overlapping intervals. The problem of finding maximum independent sets in interval graphs has been studied, for example, in the context of [[job scheduling]]: given a set of jobs that has to be executed on a computer, find a maximum set of jobs that can be executed without interfering with each other. This problem can be solved exactly in polynomial time using [[earliest deadline first scheduling]].

==== In geometric intersection graphs ====
{{Main|Maximum disjoint set}}
A geometric [[intersection graph]] is a graph in which the nodes are geometric shapes and there is an edge between two shapes if and only if they intersect. An independent set in a geometric intersection graph is just a set of disjoint (non-overlapping) shapes. The problem of finding maximum independent sets in geometric intersection graphs has been studied, for example, in the context of [[Automatic label placement]]: given a set of locations in a map, find a maximum set of disjoint rectangular labels near these locations.

Finding a maximum independent set in intersection graphs is still NP-complete, but it is easier to approximate than the general maximum independent set problem. A recent survey can be found in the introduction of {{harvtxt|Chan|Har-Peled|2012}}.

==== In d-claw-free graphs ====
A ''d-claw'' in a graph is a set of ''d''+1 vertices, one of which (the "center") is connected to the other ''d'' vertices, but the other d vertices are not connected to each other. A ''d''-[[claw-free graph]] is a graph that does not have a ''d''-claw subgraph. Consider the algorithm that starts with an empty set, and incrementally adds an arbitrary vertex to it as long as it is not adjacent to any existing vertex. In ''d''-claw-free graphs, every added vertex invalidates at most ''d'' − 1 vertices from the maximum independent set; therefore, this trivial algorithm attains a (''d'' − 1)-approximation algorithm for the maximum independent set. In fact, it is possible to get much better approximation ratios:

* Neuwohner<ref>{{Citation |last=Neuwohner |first=Meike |date=2021-06-07 |title=An Improved Approximation Algorithm for the Maximum Weight Independent Set Problem in d-Claw Free Graphs |arxiv=2106.03545 }}</ref> presented a polynomial time algorithm that, for any constant ε>0, finds a (''d''/2 − 1/63,700,992+ε)-approximation for the maximum weight independent set in a ''d''-claw free graph.
* Cygan<ref>{{Cite book |last=Cygan |first=Marek |title=2013 IEEE 54th Annual Symposium on Foundations of Computer Science |chapter=Improved Approximation for 3-Dimensional Matching via Bounded Pathwidth Local Search |date=October 2013 |chapter-url=https://ieeexplore.ieee.org/document/6686187 |pages=509–518 |doi=10.1109/FOCS.2013.61|arxiv=1304.1424 |isbn=978-0-7695-5135-7 |s2cid=14160646 }}</ref> presented a [[quasi-polynomial time]] algorithm that, for any ε>0, attains a (d+ε)/3 approximation.