Editing Independent set (graph theory) (section)

===Maximum independent sets and maximum cliques===

The independent set problem and the [[clique problem]] are complementary: a clique in ''G'' is an independent set in the [[complement graph]] of ''G'' and vice versa. Therefore, many computational results may be applied equally well to either problem. For example, the results related to the clique problem have the following corollaries:
* The independent set decision problem is [[NP-complete]], and hence it is not believed that there is an efficient algorithm for solving it.
* The maximum independent set problem is [[NP-hard]] and it is also hard to [[Approximation algorithm|approximate]].

Despite the close relationship between maximum cliques and maximum independent sets in arbitrary graphs, the independent set and clique problems may be very different when restricted to special classes of graphs. For instance, for [[dense graph|sparse graphs]] (graphs in which the number of edges is at most a constant times the number of vertices in any subgraph), the maximum clique has bounded size and may be found exactly in linear time;<ref>{{harvtxt|Chiba|Nishizeki|1985}}.</ref> however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is [[SNP (complexity)|MAXSNP-complete]], implying that, for some constant ''c'' (depending on the degree) it is [[NP-hard]] to find an approximate solution that comes within a factor of ''c'' of the optimum.<ref>{{harvtxt|Berman|Fujito|1995}}.</ref>

{{See|Clique problem#Finding maximum cliques in arbitrary graphs}}