Independent set (graph theory)

[3] As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.

Every maximum independent set also is maximal, but the converse implication does not necessarily hold.

A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary.

In a bipartite graph with no isolated vertices, the number of vertices in a maximum independent set equals the number of edges in a minimum edge covering; this is Kőnig's theorem.

For example, the results related to the clique problem have the following corollaries: 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 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;[7] however, for the same classes of graphs, or even for the more restricted class of bounded degree graphs, finding the maximum independent set is 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.

However, it can be solved more efficiently than the O(n2 2n) time that would be given by a naive brute force algorithm that examines every vertex subset and checks whether it is an independent set.

[10] For many classes of graphs, a maximum weight independent set may be found in polynomial time.

[13] For chordal graphs, a maximum weight independent set can be found in linear time.

[14] Modular decomposition is a good tool for solving the maximum weight independent set problem; the linear time algorithm on cographs is the basic example for that.

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 Poly-APX-complete, meaning it is as hard as any problem that can be approximated to a polynomial factor.

[17] In bounded degree graphs, effective approximation algorithms are known with approximation ratios 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 Δ.

[18] Approximation hardness bounds for such instances were proven in Berman & Karpinski (1999).

This problem can be solved exactly in polynomial time using earliest deadline first scheduling.

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.

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: The problem of finding a maximal independent set can be solved in polynomial time by a trivial parallel greedy algorithm .

The counting problem #IS asks, given an undirected graph, how many independent sets it contains.

[23] It is further known that, assuming that NP is different from RP, the problem cannot be tractably approximated in the sense that it does not have a fully polynomial-time approximation scheme with randomization (FPRAS), even on graphs with maximal degree six;[24] however it does have an fully polynomial-time approximation scheme (FPTAS) in the case where the maximal degree is five.

[28] They also serve as useful models for real world optimization problems, for example maximum independent set is a useful model for discovering stable genetic components for designing engineered genetic systems.