HOME

TheInfoList



OR:

In
graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, an independent set, stable set, coclique or anticlique is a set of vertices in a
graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...
, no two of which are adjacent. That is, it is a set S of vertices such that for every two vertices in S, there is no
edge Edge or EDGE may refer to: Technology Computing * Edge computing, a network load-balancing system * Edge device, an entry point to a computer network * Adobe Edge, a graphical development application * Microsoft Edge, a web browser developed by ...
connecting the two. Equivalently, each edge in the graph has at most one endpoint in S. A set is independent if and only if it is a
clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
in the graph's complement. The size of an independent set is the number of vertices it contains. Independent sets have also been called "internally stable sets", of which "stable set" is a shortening. A
maximal independent set In graph theory, a maximal independent set (MIS) or maximal stable set is an Independent set (graph theory), independent set that is not a subset of any other independent set. In other words, there is no Vertex (graph theory), vertex outside th ...
is an independent set that is not a
proper subset In mathematics, a set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset ...
of any other independent set. A maximum independent set is an independent set of largest possible size for a given graph G. This size is called the independence number of ''G'' and is usually denoted by \alpha(G). The
optimization problem In mathematics, engineering, computer science and economics Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
of finding such a set is called the maximum independent set problem. It is a
strongly NP-hard In computational complexity, strong NP-completeness is a property of computational problems that is a special case of NP-completeness. A general computational problem may have numerical parameters. For example, the input to the bin packing problem ...
problem. 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.


Properties


Relationship to other graph parameters

A set is independent if and only if it is a
clique A clique (AusE, CanE, or ; ), in the social sciences, is a small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...
in the graph’s
complement Complement may refer to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-class collections into complementary sets * Complementary color, in the visu ...
, 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, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of the mathematical field of combinatorics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in R ...
. A set is independent if and only if its complement is a
vertex cover In graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. In computer science, the problem of finding a minimum vertex cover is a classical optimizat ...
. 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 In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
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 In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
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 set In graph theory, a dominating set for a Graph (discrete mathematics), graph is a subset of its vertices, such that any vertex of is in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for ...
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 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 (at least 3, if the graph is simple) connected in a closed chain. The cycle graph with vertices is called ...
s is given by the
Perrin number In mathematics, the Perrin numbers are a doubly infinite constant-recursive sequence, constant-recursive integer sequence with Characteristic equation (calculus), characteristic equation . The Perrin numbers, named after the French engineer , bear ...
s, and the number of maximal independent sets in ''n''-vertex
path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
s is given by the
Padovan sequence In number theory, the Padovan sequence is the integer sequence, sequence of integers ''P''(''n'') defined. by the initial values P(0) = P(1) = P(2) = 1, and the recurrence relation P(n) = P(n-2)+P(n-3). The first few values of ''P''(''n'') are ...
. Therefore, both numbers are proportional to powers of 1.324718..., the
plastic ratio In mathematics, the plastic ratio is a geometrical aspect ratio, proportion, given by the unique real polynomial root, solution of the equation Its decimal expansion begins as . The adjective ''plastic'' does not refer to Plastic, the artifici ...
.


Finding independent sets

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, several
computational problems In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computatio ...
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 In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted by 1 and 0, whereas ...
: 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 In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
to problems related to independent sets.


Maximum independent sets and maximum cliques

The independent set problem and the
clique problem In computer science, the clique problem is the computational problem of finding cliques (subsets of vertices, all adjacent to each other, also called complete subgraphs) in a graph. It has several different formulations depending on which c ...
are complementary: a clique in ''G'' is an independent set in the
complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of ...
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 In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...
, and hence it is not believed that there is an efficient algorithm for solving it. * The maximum independent set problem is
NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
and it is also hard to
approximate An approximation is anything that is intentionally similar but not exactly equal to something else. Etymology and usage The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ...
. 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 In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
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(''n''2 2''n'') 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.1996''n'') using polynomial space. When restricted to graphs with maximum degree 3, it can be solved in time O(1.0836''n''). For many classes of graphs, a maximum weight independent set may be found in polynomial time. Famous examples are
claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...
s, ''P''5-free graphs and
perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...
s. For chordal graphs, a maximum weight independent set can be found in linear time.
Modular decomposition In Graph (discrete mathematics), graph theory, the modular decomposition is a decomposition of a Graph (discrete mathematics), graph into subsets of Vertex (graph theory), vertices called modules. A ''module'' is a generalization of a Connected c ...
is a good tool for solving the maximum weight independent set problem; the linear time algorithm on
cograph In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s 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 In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
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 graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), 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 may be approximated to within any approximation ratio ''c'' < 1 in polynomial time; similar
polynomial-time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an inst ...
s exist in any family of graphs closed under taking minors.


In bounded degree graphs

In bounded degree graphs, effective approximation algorithms are known with
approximation ratio In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned sol ...
s that are constant for a fixed value of the maximum degree; for instance, a
greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
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 Î”. Approximation hardness bounds for such instances were proven in . Indeed, even Max Independent Set on 3-regular 3-edge-colorable graphs is
APX-complete In computational complexity theory, the class APX (an abbreviation of "approximable") is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant (or constant-factor a ...
.


In interval intersection graphs

An
interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. In ...
is a graph in which the nodes are 1-dimensional intervals (e.g. time intervals) and there is an edge between two intervals if and only if they intersect. An independent set in an interval graph is just a set of non-overlapping intervals. The problem of finding maximum independent sets in interval graphs has been studied, for example, in the context of
job scheduling A job scheduler is a computer application for controlling unattended background program execution of job (computing), jobs. This is commonly called batch scheduling, as execution of non-interactive jobs is often called batch processing, though tr ...
: given a set of jobs that has to be executed on a computer, find a maximum set of jobs that can be executed without interfering with each other. This problem can be solved exactly in polynomial time using
earliest deadline first scheduling Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) th ...
.


In geometric intersection graphs

A geometric
intersection graph In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types o ...
is a graph in which the nodes are geometric shapes and there is an edge between two shapes if and only if they intersect. An independent set in a geometric intersection graph is just a set of disjoint (non-overlapping) shapes. The problem of finding maximum independent sets in geometric intersection graphs has been studied, for example, in the context of
Automatic label placement Automatic label placement, sometimes called text placement or name placement, comprises the computer methods of placing labels automatically on a map or chart. This is related to the typographic design of such labels. The typical features depicted ...
: given a set of locations in a map, find a maximum set of disjoint rectangular labels near these locations. Finding a maximum independent set in intersection graphs is still NP-complete, but it is easier to approximate than the general maximum independent set problem. A recent survey can be found in the introduction of .


In d-claw-free graphs

A ''d-claw'' in a graph is a set of ''d''+1 vertices, one of which (the "center") is connected to the other ''d'' vertices, but the other d vertices are not connected to each other. A ''d''-
claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...
is a graph that does not have a ''d''-claw subgraph. Consider the algorithm that starts with an empty set, and incrementally adds an arbitrary vertex to it as long as it is not adjacent to any existing vertex. 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: * Neuwohner presented a polynomial time algorithm that, for any constant ε>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 In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant c such that the worst-case running ...
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 In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...
by a trivial parallel
greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
. All maximal independent sets can be found in time O(3''n''/3) = O(1.4423''n'').


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 In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of f ...
-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 In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an inst ...
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 graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
s, is also
♯P In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of f ...
-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 In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations ...
of many theoretical problems. 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.


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 In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a graph. The assignment is subject to certain constraints, such as that no two adjacent elements have the same color. Graph coloring i ...
is a partition of the vertex set into independent sets.


Notes


References

*. *. * *. *. *. *. *. *. *. *. *. * . *. *. *. *. *. *. *. *. *. * *. *. *. *. *.


External links

*
Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring
{{Webarchive, url=https://web.archive.org/web/20130529163947/http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm , date=2013-05-29
Independent Set and Vertex Cover
Hanan Ayad. Graph theory objects NP-complete problems Computational problems in graph theory