FindIndependentVertexSet
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.
FindIndependentVertexSet[g,{n}]
finds an independent vertex set with exactly n vertices.
FindIndependentVertexSet[g,{nmin,nmax}]
finds an independent vertex set containing between nmin and nmax vertices.
FindIndependentVertexSet[g,nspec,s]
finds at most s independent vertex sets.
FindIndependentVertexSet[{g,v},…]
finds independent sets that include the vertex v only.
FindIndependentVertexSet[{vw,…},…]
uses rules vw to specify the graph g.
Details
- 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”.
Examples
open allclose allBasic Examples (2)
Scope (14)
FindIndependentVertexSet works with undirected graphs:
Find a largest independent vertex set:
An independent vertex set containing exactly 3 vertices:
An independent vertex set containing at most 2 vertices:
An independent vertex set containing between 3 and 5 vertices:
A largest independent vertex set that includes a given vertex:
Find all independent vertex sets in a graph:
Use rules to specify the graph:
FindIndependentVertexSet gives an empty list if there is no independent vertex set:
FindIndependentVertexSet works with large graphs:
Applications (3)
Highlight all independent vertex sets in a graph:
In a franchise service network, vertices are store locations and two stores are connected if they are close enough to interfere sales. Having a store at NorthPoint, find possible locations for new stores:
Possible locations for new stores:
Find members of the Dow Jones Industrial whose returns are not highly correlated:
First compute the correlation of returns since the beginning of this year:
Build a graph with edges between stocks having a correlation coefficient above a chosen 
:
Properties & Relations (4)
Test whether a set of vertices is an independent vertex set, using IndependentVertexSetQ:
The complement of an independent vertex set is a vertex cover:
The complement subgraph given by an independent vertex set is complete:
Bipartite graphs have equal-length edge covers and independent vertex sets:
Text
Wolfram Research (2010), FindIndependentVertexSet, Wolfram Language function, https://reference.wolfram.com/language/ref/FindIndependentVertexSet.html (updated 2015).
CMS
Wolfram Language. 2010. "FindIndependentVertexSet." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindIndependentVertexSet.html.
APA
Wolfram Language. (2010). FindIndependentVertexSet. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindIndependentVertexSet.html