Editing Independent set (graph theory) (section)

=== Exact algorithms ===
The maximum independent set problem is NP-hard. However, it can be solved more efficiently than the O(''n''<sup>2</sup>&nbsp;2<sup>''n''</sup>) time that would be given by a naive [[brute-force search|brute force algorithm]] that examines every vertex subset and checks whether it is an independent set.

As of 2017 it can be solved in time O(1.1996<sup>''n''</sup>) using polynomial space.<ref>{{harvtxt|Xiao|Nagamochi|2017}}</ref> When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836<sup>''n''</sup>).<ref>{{harvtxt|Xiao|Nagamochi|2013}}</ref>

For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are [[claw-free graph]]s,<ref>{{harvtxt|Minty|1980}},{{harvtxt|Sbihi|1980}},{{harvtxt|Nakamura|Tamura|2001}},{{harvtxt|Faenza|Oriolo|Stauffer|2014}},{{harvtxt|Nobili|Sassano|2015}}</ref> ''P''<sub>5</sub>-free graphs<ref>{{harvtxt|Lokshtanov|Vatshelle|Villanger|2014}}</ref> and [[perfect graph]]s.<ref>{{harvtxt|Grötschel|Lovász|Schrijver|1993|loc=Chapter 9: Stable Sets in Graphs}}</ref> For [[chordal graph]]s, a maximum weight independent set can be found in linear time.<ref>{{harvtxt|Frank|1976}}</ref>

[[Modular decomposition]] is a good tool for solving the maximum weight independent set problem; the linear time algorithm on [[cograph]]s is the basic example for that. Another important tool are [[clique separator]]s as described by Tarjan.<ref>{{harvtxt|Tarjan|1985}}</ref>

[[Kőnig's theorem (graph theory)|Kőnig's theorem]] implies that in a [[bipartite graph]] the maximum independent set can be found in polynomial time using a bipartite matching algorithm.