IndependenceNumber - Maple Help

GraphTheory

 IndependenceNumber
 compute independence number
 MaximumIndependentSet
 find independent set

 Calling Sequence IndependenceNumber(G) IndependenceNumber(G, opt) MaximumIndependentSet(G) MaximumIndependentSet(G, opt)

Parameters

 G - graph opt - (optional) equation of the form method = m, where m is exact or greedy

Description

 • 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).

Definitions

 • 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.

Details

 • 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.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{CompleteGraph}\left(3,4\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 7 vertices and 12 edge\left(s\right)}}$ (1)
 > $\mathrm{DrawGraph}\left(G\right)$
 > $\mathrm{IndependenceNumber}\left(G\right)$
 ${4}$ (2)
 > $\mathrm{MaximumIndependentSet}\left(G\right)$
 $\left[{4}{,}{5}{,}{6}{,}{7}\right]$ (3)

This is equivalent to the maximum clique problem on the complement of $G$.

 > $C≔\mathrm{GraphComplement}\left(G\right):$
 > $\mathrm{DrawGraph}\left(C\right)$
 > $\mathrm{CliqueNumber}\left(C\right)$
 ${4}$ (4)
 > $\mathrm{MaximumClique}\left(C\right)$
 $\left[{4}{,}{5}{,}{6}{,}{7}\right]$ (5)

In this case, the greedy algorithm also finds the optimum.

 > $\mathrm{IndependenceNumber}\left(G,'\mathrm{method}'='\mathrm{greedy}'\right)$
 ${4}$ (6)
 > $\mathrm{MaximumIndependentSet}\left(G,'\mathrm{method}'='\mathrm{greedy}'\right)$
 $\left[{4}{,}{5}{,}{6}{,}{7}\right]$ (7)

Compatibility

 • The GraphTheory[IndependenceNumber] and GraphTheory[MaximumIndependentSet] commands were updated in Maple 2019.
 • The method option was introduced in Maple 2019.