GraphTheory
GreedyClique
find clique using greedy algorithm
GreedyIndependentSet
find independent set using greedy algorithm
Calling Sequence
Parameters
Description
Examples
References
Compatibility
GreedyClique(G, opts)
GreedyIndependentSet(G, opts)
G
-
graph
opts
(optional) equation of the form iterations = n or thresholds = t, where n is a positive integer and t is a non-empty list of numerical values in the closed interval 0,1
GreedyClique attempts to find a large clique of the graph G. It returns the set of vertex labels corresponding to the clique it finds.
GreedyIndependentSet attempts to find a large independent set of the graph G. It returns the set of vertex labels corresponding to the independent set it finds. It does this by calling GreedyClique on the complement of G.
The problem of finding a maximum clique for a graph is NP-complete, meaning that no polynomial-time algorithm is presently known that can return a clique of the largest possible size for a given graph. An exhaustive search is implemented in the MaximumClique command, which will take an exponential time on some graphs. By contrast, the algorithm implemented in GreedyClique takes polynomial time, but it may return a clique that is not of maximum size.
The algorithm is a so-called GRASP process, which stands for greedy randomized adaptive search procedure. It consists of an outer loop, of which each iteration tries to find a large clique; the procedure then returns the largest clique found. A single iteration of this outer loop consists of two steps:
In step 1, the procedure finds a clique that is maximal, i.e., a clique that cannot be extended to a larger clique. (This is different from a maximum clique, as discussed in a bullet point above.) This is done in a loop, by starting with the empty set of vertices, and then in each iteration, selecting a vertex to add that is connected to all previously selected vertices. Among all such vertices connected to all previously selected vertices, let d and D be the minimal and maximal degrees; the procedure will select a vertex whose degree is at least d+θD−d, where θ is a numerical constant between 0 and 1 that is a parameter for the algorithm. The value of θ can be controlled by the thresholds option: its value is a list of such constants, one for each iteration of the outer loop.
In step 2, the process tries to find a larger clique by finding a vertex it can remove from the clique and replace by two vertices that can be added. It continues doing this (and extending the clique to a maximal clique, if necessary) until no such change can be made anymore.
As explained above, you can increase or decrease the number of iterations of the outer loop by passing the thresholds parameter, specifying the values for the parameter θ in each iteration. If the thresholds parameter is not specified, then the number of iterations of the outer loop is specified by the iterations parameter; the thresholds used are then equally spread out from 0 to 1 - they are the numbers iiterations−1, as i ranges from 0 to iterations−1. If the iterations parameter is also not specified, its default value is 5, so the thresholds used are by default 0,14,12,34,1. If both the thresholds and iterations parameters are specified, then the iterations parameter is ignored.
withGraphTheory:
withRandomGraphs:
Here we have a random graph that is quite dense. Each possible edge of this graph with 1000 vertices is included with probability 0.95.
G1≔RandomGraph1000,0.95:
c1≔GreedyCliqueG1
c1≔25,26,42,86,96,105,115,150,154,166,172,176,177,191,204,206,207,219,229,230,236,238,243,262,296,304,313,314,316,324,336,355,356,366,375,385,391,399,406,412,420,422,431,432,442,462,474,482,487,488,494,506,518,522,525,526,552,557,565,572,584,593,595,604,622,627,659,668,673,688,696,704,716,727,759,794,803,808,818,845,851,862,902,906,917,924,926,937,944,965,984,985,986
IsCliqueG1,c1
true
numelemsc1
93
Theoretical considerations show that the expected number of cliques of size k in this graph is 1000k0.95k2. This number dips below 1 around k=120, which suggests that the maximum clique should be of size around 120.
We try the same thing with a very sparse graph. We specify that Maple should run 50 iterations instead of the normal 5.
G2≔RandomGraph3000,0.01:
c2≔GreedyCliqueG2,iterations=50
c2≔260,1557,2405
IsCliqueG2,c2
numelemsc2
3
The same argument as above, now with the formula 3000k0.01k2, suggests that the maximum clique in this graph should be of size about 4.
Finally, we try a regular graph.
G3≔RandomRegularGraph100,30
G3≔Graph 1: an undirected graph with 100 vertices and 1500 edge(s)
By setting the infolevel entry for GreedyClique (or for GraphTheory), we can see what happens for each iteration. We specify different thresholds to see if this has any effect: we run twenty iterations with threshold 0 (pick any suitable vertex) and twenty with threshold 1 (pick only vertices with the maximal degree).
infolevelGreedyClique≔4
c3≔GreedyCliqueG3,thresholds=`$`0,20,`$`1,20
GreedyClique: step 1: found clique of size 5 with parameter 0
GreedyClique: step 2: clique grown to size 5
GreedyClique: step 1: found clique of size 3 with parameter 0
GreedyClique: step 2: clique grown to size 4
GreedyClique: step 1: found clique of size 4 with parameter 0
GreedyClique: step 2: clique grown to size 6
GreedyClique: step 1: found clique of size 6 with parameter 0
GreedyClique: step 1: found clique of size 5 with parameter 1
GreedyClique: step 1: found clique of size 4 with parameter 1
GreedyClique: step 1: found clique of size 3 with parameter 1
GreedyClique: step 1: found clique of size 6 with parameter 1
c3≔38,45,50,54,60,87
We can also find an independent set in the same graph.
i3≔GreedyIndependentSetG3,iterations=8
GreedyClique: step 1: found clique of size 9 with parameter 0
GreedyClique: step 2: clique grown to size 11
GreedyClique: step 1: found clique of size 10 with parameter 1/7
GreedyClique: step 2: clique grown to size 10
GreedyClique: step 1: found clique of size 9 with parameter 2/7
GreedyClique: step 1: found clique of size 9 with parameter 3/7
GreedyClique: step 2: clique grown to size 12
GreedyClique: step 1: found clique of size 11 with parameter 4/7
GreedyClique: step 1: found clique of size 11 with parameter 5/7
GreedyClique: step 1: found clique of size 9 with parameter 6/7
GreedyClique: step 1: found clique of size 11 with parameter 1
i3≔6,9,20,30,35,49,65,68,71,77,89,91
We show the resulting clique and independent set.
HighlightSubgraphG3,InducedSubgraphG3,c3,edgestylesheet=color=red,vertexstylesheet=color=red
HighlightSubgraphG3,InducedSubgraphG3,i3,edgestylesheet=color=green,vertexstylesheet=color=green
Warning, {} is not an edge of the graph.
DrawGraphG3,style=spring
T.A. Feo, M.G.C. Resende, and S.H. Smith. A greedy randomized adaptive search procedure for maximum independent set. Operations Research, 42:860–878, 1994.
The GraphTheory[GreedyClique] and GraphTheory[GreedyIndependentSet] commands were introduced in Maple 2019.
For more information on Maple 2019 changes, see Updates in Maple 2019.
See Also
GreedyColor
IsClique
MaximumClique
Download Help Document
