All Topics  
Independent set

 

 
   Email Print
   Bookmark   Link
 

 

Independent set
 
 
  Topics Independent set Topic Home

In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, 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 no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in , there is no edge
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
 connecting the two. Equivalently, each edge in the graph has at most one endpoint in V. 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....
 is an independent set such that adding any other node to the set forces the set to contain an edge.

A maximum independent set is a largest independent set for a given graph and its size is denoted .






Discussion
Ask a question about 'Independent set'
Start a new discussion about 'Independent set'
Answer questions from other users
Full Discussion Forum



Encyclopedia


In graph theory
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
, 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 no two of which are adjacent. That is, it is a set V of vertices such that for every two vertices in , there is no edge
Graph theory

In mathematics and computer science, graph theory is the study of graph : mathematical structures used to model pairwise relations between objects from a certain collection....
 connecting the two. Equivalently, each edge in the graph has at most one endpoint in V. 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....
 is an independent set such that adding any other node to the set forces the set to contain an edge.

A maximum independent set is a largest independent set for a given graph and its size is denoted . The problem of finding such a set is called the maximum independent set problem and is an NP-complete
NP-complete

In computational complexity theory, the complexity class NP-complete is a class of problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
 problem. As such, it is very unlikely that an efficient algorithm for finding a maximum independent set of 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....
 exists.

The problem of deciding if a graph has an independent set of a particular size is the independent set problem
Independent set problem

In mathematics, the independent set problem is a well-known problem in graph theory and combinatorics. The independent set problem is known to be NP-complete....
. It is computationally equivalent to deciding if a graph has a clique
Clique (graph theory)

In graph theory, a clique in an undirected graph G is a set of vertex V such that for every two vertices in V, there exists an Edge connecting the two....
 of a particular size. This follows from the fact that if a graph has an independent set of size k, then its complement (the graph on the same vertex set, but complementary edge set) has a clique of size k. The decision version of Independent Set (and consequently, clique
Clique (graph theory)

In graph theory, a clique in an undirected graph G is a set of vertex V such that for every two vertices in V, there exists an Edge connecting the two....
) is known to be NP-complete
NP-complete

In computational complexity theory, the complexity class NP-complete is a class of problems having two properties:* Any given solution to the problem can be verified quickly ; the set of problems with this property is called NP ....
.

A maximum independent set should not be confused with a maximal independent set. A maximal independent set is an independent set which is not contained in any larger independent set. The problem of finding a maximal independent set can be solved in polynomial time
Polynomial time

In computational complexity theory, polynomial time refers to the computation time of a problem where the run time, , is no greater than a polynomial function of the problem size, n....
 by a trivial greedy algorithm
Greedy algorithm

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

Properties


Relationship to other graph parameters


A set is independent if and only if it is a clique
Clique

A clique is an exclusive group of people who share interests, views, purposes, patterns of behavior, or ethnicity. A clique as a reference group can be either normative or comparative....
 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 for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. Problems in Ramsey theory typically ask a question of the form: how many elements of some structure must there be to guarantee that a particular property will hold?...
.

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

In the mathematics discipline of graph theory, a vertex cover of a graph is a set of vertices such that each edge of the graph touches at least one element of the set....
. The sum of and the size minimum vertex cover is the number of vertices in the graph.

In a bipartite graph
Bipartite graph

In the mathematics field of graph theory, a bipartite graph is a graph whose vertex 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.

Maximal independent set


An independent set that is not the subset of another independent set is called maximal. Such sets are dominating set
Dominating 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. Graphs contain at most 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 is a graph that consists of a single path , or in other words, some number of vertices connected in a closed chain....
s is given by the Perrin number
Perrin number

In mathematics, the Perrin numbers are defined by the recurrence relationandThe series beginsThe number of different maximal independent sets in an n-vertex cycle graph is counted by the nth Perrin number ....
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 vertex such that from each of its vertices there is an edge to the next vertex in the sequence....
 is given by the Padovan sequence
Padovan sequence

The Padovan sequence is the sequence of integers P defined by the initial valuesand the recurrence relationThe first few values of P are...
. Therefore, both numbers are proportional to powers of 1.324718, the plastic number
Plastic number

In math, the plastic number is the unique real solution of the cubic equationand has the valuewhich is approximately 1.324717957244746025960908854 ....
. Listing the maximal independent sets can be used as a subroutine for many algorithms that deal with NP-hard problem.

See also

  • an edge independent set is called Matching
    Matching

    In the mathematical discipline of graph theory a matching or edge-independent set in a graph is a set of edges without common vertex . It may also be an entire graph consisting of edges without common vertices....


External links