Independent set (graph theory)

Encyclopedia

In graph theory

, an

in a graph

, no two of which are adjacent. That is, it is a set

A maximal independent set

is an independent set such that adding any other vertex to the set forces the set to contain an edge.

A

optimization problem

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

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

. The sum of

In a bipartite graph

, 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

.

s. Every graph contains at most 3

The number of maximal independent sets in

s is given by the Perrin number

s, and the number of maximal independent sets in

is given by the Padovan sequence

. Therefore, both numbers are proportional to powers of 1.324718, the plastic number

.

, several computational problems related to independent sets have been studied.

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.

The independent set problem and the clique problem

are complementary: a clique in

of

are polynomially equivalent: one can find a maximum independent set in a graph by finding a maximum clique in its complement graph

, so many authors do not carefully distinguish between the two problems. Both problems are NP-complete

, so it is unlikely that they can be solved in polynomial time. Nevertheless the maximum independent set problem can be solved more efficiently than the O(

that examines every vertex subset and checks whether it is an independent set. An algorithm of solves the problem in time O(2

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

to find an approximate solution that comes within a factor of

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

In some classes of graphs, including claw-free graphs and perfect graph

s, the maximum independent set may be found in polynomial time. In planar graph

s, the maximum independent set remains NP-complete to find exactly but may be approximated to within any approximation ratio

s exist in any family of graphs closed under taking minors

.

. All maximal independent sets can be found in time O(3

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, an

**independent set**or**stable set**is a set of verticesVertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

in a graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

, no two of which are adjacent. That is, it is a set

*I*of vertices such that for every two vertices in*I*, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in*I*. The size of an independent set is the number of vertices it contains.A maximal independent set

Maximal independent set

In graph theory, a maximal independent set or maximal stable set is an independent set that is not a subset of any other independent set. That is, it is a set S such that every edge of the graph has at least one endpoint not in S and every vertex not in S has at least one neighbor in S...

is an independent set such that adding any other vertex to the set forces the set to contain an edge.

A

**maximum independent set**is a largest independent set for a given graph*G*and its size is denoted*α*(*G*). The problem of finding such a set is called the**maximum independent set problem**and is an NP-hardNP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

optimization problem

Optimization problem

In mathematics and computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. Optimization problems can be divided into two categories depending on whether the variables are continuous or discrete. An optimization problem with discrete...

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

### Relationship to other graph parameters

A set is independent if and only if it is a cliqueClique (graph theory)

In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...

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

Ramsey theory

Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...

.

A set is independent if and only if its complement is a vertex cover

Vertex cover

In the mathematical discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set....

. The sum of

*α*(*G*) and the size of a minimum vertex cover*β*(*G*) is the number of vertices in the graph.In a bipartite graph

Bipartite graph

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...

, 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

König's theorem (graph theory)

In the mathematical area of graph theory, König's theorem, proved by Dénes Kőnig in 1931, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs...

.

### Maximal independent set

An independent set that is not the subset of another independent set is called*maximal*. Such sets are dominating setDominating set

In graph theory, a dominating set for a graph G = is a subset D of V such that every vertex not in D is joined to at least one member of D by some edge...

s. Every graph contains at most 3

^{n/3}maximal independent sets, but many graphs have far fewer.The number of maximal independent sets in

*n*-vertex cycle graphCycle graph

In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...

s is given by the Perrin number

Perrin number

In mathematics, the Perrin numbers are defined by the recurrence relationandThe sequence of Perrin numbers starts withThe number of different maximal independent sets in an n-vertex cycle graph is counted by the nth Perrin number.-History:...

s, and the number of maximal independent sets in

*n*-vertex path graphsPath (graph theory)

In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...

is given by the Padovan sequence

Padovan sequence

The Padovan sequence is the sequence of integers P defined by the initial valuesP=P=P=1,and the recurrence relationP=P+P.The first few values of P are...

. Therefore, both numbers are proportional to powers of 1.324718, the plastic number

Plastic number

In mathematics, the plastic number ρ is a mathematical constant which is the unique real solution of the cubic equationx^3=x+1\, ....

.

## Finding independent sets

In computer scienceComputer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

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

The independent set problem and the clique problem

Clique problem

In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....

are complementary: a clique in

*G*is an independent set in the complement graphComplement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

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 decision problem is NP-completeNP-completeIn computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

, and hence it is not believed that there is an efficient algorithm for solving it. - The maximum independent set problem is NP-hardNP-hardNP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

and it is also hard to approximateApproximation algorithmIn computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...

.

### Finding maximum independent sets

The maximum independent set problem and the maximum clique problemClique problem

In computer science, the clique problem refers to any of the problems related to finding particular complete subgraphs in a graph, i.e., sets of elements where each pair of elements is connected....

are polynomially equivalent: one can find a maximum independent set in a graph by finding a maximum clique in its complement graph

Complement graph

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...

, so many authors do not carefully distinguish between the two problems. Both problems are NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

, so it is unlikely that they can be solved in polynomial time. Nevertheless the maximum independent set problem can be solved more efficiently than the O(

*n*^{2}2^{n}) time that would be given by a naive brute force algorithmBrute-force search

In computer science, brute-force search or exhaustive search, also known as generate and test, is a trivial but very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's...

that examines every vertex subset and checks whether it is an independent set. An algorithm of solves the problem in time O(2

^{0.276n}); see also .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

Dense graph

In mathematics, a dense graph is a graph in which the number of edges is close to the maximal number of edges. The opposite, a graph with only a few edges, is a sparse graph...

(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

SNP (complexity)

In computational complexity theory, SNP is a complexity class containing a limited subset of NP based on its logical characterization in terms of graph-theoretical properties...

, implying that, for some constant

*c*(depending on the degree) it is NP-hardNP-hard

NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...

to find an approximate solution that comes within a factor of

*c*of the optimum. However, effective approximation algorithms are known with approximation ratios that are worse than this threshold; for instance, a greedy algorithmGreedy algorithm

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

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

In some classes of graphs, including claw-free graphs and perfect graph

Perfect graph

In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph....

s, the maximum independent set may be found in polynomial time. In planar graph

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

s, the maximum independent set remains NP-complete to find exactly but may be approximated to within any approximation ratio

*c*< 1 in polynomial time; similar polynomial-time approximation schemePolynomial-time approximation scheme

In computer science, a polynomial-time approximation scheme is a type of approximation algorithm for optimization problems ....

s exist in any family of graphs closed under taking minors

Minor (graph theory)

In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G....

.

### Finding maximal independent sets

The problem of finding a maximal independent set can be solved in polynomial time by a trivial greedy algorithmGreedy algorithm

A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....

. All maximal independent sets can be found in time O(3

^{n/3}).## See also

- An independent set of edges is a set of edges of which no two have a vertex in common. It is usually called a matching.
- A vertex coloring is a partition of the vertex set into independent sets.