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
What kind of issue would you like to report? (Optional)