Independent set (graph theory)
Encyclopedia
In graph theory
, an independent set or stable set is a set of vertices
in a graph
, 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
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-hard
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 α(G) and the size of a minimum vertex cover β(G) is the number of vertices in the graph.
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 3n/3 maximal independent sets, but many graphs have far fewer.
The number of maximal independent sets in n-vertex cycle graph
s is given by the Perrin number
s, 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 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 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:
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(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. An algorithm of solves the problem in time O(20.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
(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. However, effective approximation algorithms are known with approximation ratios that are worse than this threshold; 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 Δ.
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 c < 1 in polynomial time; similar polynomial-time approximation scheme
s exist in any family of graphs closed under taking minors
.
. All maximal independent sets can be found in time O(3n/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 vertices
Vertex (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-hard
NP-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 3n/3 maximal independent sets, but many graphs have far fewer.
The number of maximal independent sets in n-vertex cycle graph
Cycle 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 graphs
Path (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 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...
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(n2 2n) time that would be given by a naive brute force algorithm
Brute-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(20.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-hard
NP-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 algorithm
Greedy 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 scheme
Polynomial-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(3n/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.