Editing Independent set (graph theory) (section)

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