FindIndependentVertexSet

FindIndependentVertexSet[g]
finds an independent vertex set of the graph g with a maximum number of vertices.

FindIndependentVertexSet[g,n]
finds an independent vertex set with at most n vertices.

FindIndependentVertexSet[g,{n}]
finds an independent vertex set with exactly n vertices.

FindIndependentVertexSet[g,{nmin,nmax}]
finds an independent vertex set containing between and vertices.

FindIndependentVertexSet[g,nspec,s]
finds at most s independent vertex sets.

FindIndependentVertexSet[{g,v},]
finds independent sets that include the vertex v only.

DetailsDetails

Background
Background

  • FindIndependentVertexSet finds one or more maximal independent vertex sets in a graph, returning them as a list of vertex lists. Here, an independent vertex set is a set of vertices such that no two vertices in the set are connected by an edge. Independent vertex sets have found applications in finance, coding theory, map labeling, pattern recognition, social networks, molecular biology, and scheduling.
  • There are two especially important types of independent vertex sets: maximum and maximal. Note these are not equivalent. A maximum independent vertex set is a vertex set containing the largest possible number of vertices for a given graph. In contrast, a maximal independent vertex set is an independent vertex set that cannot be extended by including one more adjacent vertices, meaning it is not a subset of a larger independent vertex set. A maximum independent vertex set is therefore always maximal, but the converse is not necessarily true.
  • FindIndependentVertexSet can find maximal independent vertex sets of different sizes. FindIndependentVertexSet can also find a single maximal independent vertex sets of specified size, a specified number of maximal independent vertex sets, or all such sets.
  • FindIndependentVertexSet[g] finds a single maximum independent vertex set of a graph g, FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],s] finds at most s, and FindIndependentVertexSet[g,Length/@FindIndependentVertexSet[g],All] finds all such sets. The size of a maximum independent vertex set of a graph g is known as its (vertex) independence number. The problem of finding a maximum independent vertex set (and hence independence number) of a given graph is NP-complete, meaning computation can be exponentially slow.
  • FindIndependentVertexSet[g,Infinity] finds a single maximal independent vertex set of a graph g, FindIndependentVertexSet[g,Infinity,s] finds at most s, and FindIndependentVertexSet[g,Infinity,All] finds all such sets.
  • A set of vertices can be tested to see if it is independent (without the requirement that it also be maximal) using IndependentVertexSetQ. An independent vertex set corresponds to the complement of a vertex cover (cf. FindVertexCover). A maximal independent vertex set of a graph is equivalent to a maximal clique on the GraphComplement (cf. FindClique). FindIndependentEdgeSet applies the same concept as FindIndependentVertexSet to edges, with the resulting independent edge sets also being known as matchings.
Introduced in 2010
(8.0)
| Updated in 2014
(10.0)