Independent set (graph theory)

Relationship to other graph parameters A set is independent if and only if it is a clique in the graph’s complement, so the two concepts are complementary. In fact, sufficiently large graphs with no large cliques have large independent sets, a theme that is explored in Ramsey theory. A set is independent if and only if its complement is a vertex cover. Therefore, the sum of the size of the largest independent set \alpha(G) and the size of a minimum vertex cover \beta(G) is equal to the number of vertices in the graph. A vertex coloring of a graph G corresponds to a partition of its vertex set into independent subsets. Hence the minimal number of colors needed in a vertex coloring, the chromatic number \chi(G), is at least the quotient of the number of vertices in G and the independent number \alpha(G). 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. Maximal independent set An independent set that is not a proper subset of another independent set is called maximal. Such sets are dominating sets. Every graph contains at most 3n/3 maximal independent sets, but many graphs have far fewer. The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence. Therefore, both numbers are proportional to powers of 1.324718..., the plastic ratio. ==Finding independent sets==

In computer science, several computational problems related to independent sets have been studied. • In the maximum independent set problem, the input is an undirected graph, and the output is a maximum independent set in the graph. If there are multiple maximum independent sets, only one need be output. This problem is sometimes referred to as "vertex packing". • In the maximum-weight independent set problem, the input is an undirected graph with weights on its vertices and the output is an independent set with maximum total weight. The maximum independent set problem is the special case in which all weights are one. • In the maximal independent set listing problem, the input is an undirected graph, and the output is a list of all its maximal independent sets. The maximum independent set problem may be solved using as a subroutine an algorithm for the maximal independent set listing problem, because the maximum independent set must be included among all the maximal independent sets. • In the independent set decision problem, the input is an undirected graph and a number k, and the output is a Boolean value: true if the graph contains an independent set of size k, and false otherwise. The first three of these problems are all important in practical applications; the independent set decision problem is not, but is necessary in order to apply the theory of NP-completeness to problems related to independent sets. 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 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 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; 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. Exact algorithms The maximum independent set problem is NP-hard. 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. As of 2017 it can be solved in time O(1.1996n) using polynomial space. When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836n). For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are claw-free graphs, P5-free graphs and perfect graphs. For chordal graphs, a maximum weight independent set can be found in linear time. 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. Another important tool are clique separators as described by Tarjan. 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. 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 Poly-APX-complete, meaning it is as hard as any problem that can be approximated to a polynomial factor. However, there are efficient approximation algorithms for restricted classes of graphs. In planar graphs In planar graphs, the maximum independent set may be approximated to within any approximation ratio c 0, finds a (d/2 − 1/63,700,992+ε)-approximation for the maximum weight independent set in a d-claw free graph. • Cygan presented a quasi-polynomial time algorithm that, for any ε>0, attains a (d+ε)/3 approximation. Finding maximal independent sets The problem of finding a maximal independent set can be solved in polynomial time by a trivial parallel greedy algorithm . All maximal independent sets can be found in time O(3n/3) = O(1.4423n). Counting independent sets The counting problem #IS asks, given an undirected graph, how many independent sets it contains. This problem is intractable, namely, it is ♯P-complete, already on graphs with maximal degree three. 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; however it does have an fully polynomial-time approximation scheme (FPTAS) in the case where the maximal degree is five. The problem #BIS, of counting independent sets on bipartite graphs, is also ♯P-complete, already on graphs with maximal degree three. It is not known whether #BIS admits a FPRAS. The question of counting maximal independent sets has also been studied. == Applications ==

The maximum independent set and its complement, the minimum vertex cover problem, is involved in proving the computational complexity of many theoretical problems. == See also ==