compute independence number
find independent set
(optional) equation of the form method = m, where m is exact or greedy
IndependenceNumber returns the independence number of the graph G.
MaximumIndependentSet returns a list of vertices comprising a maximum independent set of G.
The strategy is a branch-and-bound backtracking algorithm using the greedy color bound (see Kreher and Stinson, 1999).
An independent set of a graph G is a subset S of the vertices of G, with the condition that if any vertices v1 and v2 are both members of S, the graph G must not contain an edge between them. An independent set of G is a clique of the complement of G.
A maximum independent set of G is an independent set of maximum size for the graph G.
The independence number of G is the cardinality of a maximum independent set of G. This is equal to the clique number of the complement of G.
The problem of finding a maximum independent set for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known. The exhaustive search will take an exponential time on some graphs. For a faster algorithm that usually, but not always, returns a relatively large clique see GreedyIndependentSet. This algorithm can also be selected by using the method = greedy option. The default is method = exact.
G ≔ CompleteGraph⁡3,4
G≔Graph 1: an undirected graph with 7 vertices and 12 edge(s)
This is equivalent to the maximum clique problem on the complement of G.
C ≔ GraphComplement⁡G:
In this case, the greedy algorithm also finds the optimum.
The GraphTheory[IndependenceNumber] and GraphTheory[MaximumIndependentSet] commands were updated in Maple 2019.
The method option was introduced in Maple 2019.
For more information on Maple 2019 changes, see Updates in Maple 2019.
Download Help Document