finds an independent vertex set of the graph g with a maximum number of vertices.
finds an independent vertex set with at most n vertices.
finds an independent vertex set with exactly n vertices.
finds an independent vertex set containing between nmin and nmax vertices.
finds at most s independent vertex sets.
finds independent sets that include the vertex v only.
uses rules vw to specify the graph g.
- FindIndependentVertexSet is also known as stable set or maximal independent set.
- An independent vertex set is a maximal set of vertices that are never incident to the same edge.
- FindIndependentVertexSet returns a list of vertices.
- FindIndependentVertexSet will return an empty list if there is no independent vertex set.
- FindIndependentVertexSet[…,nspec,All] finds all the independent vertex sets.
- For weighted graphs, FindIndependentVertexSet gives a set of vertices with maximum sum of vertex weights.
- FindIndependentVertexSet works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.
Background & Context
- 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.
- Not-necessarily-maximal independent vertex sets cannot be found directly using FindIndependentVertexSet but can be simplistically enumerated by taking the union over the collection of all subsets of all maximal independent vertex 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”.