# Cliques, Independent Sets The functions given here are not applicable to digraphs. A *clique* of a graph $G$ is a complete subgraph of $G$. A *maximal clique* is a clique which is not contained in any other clique. A *maximum clique* is a maximal clique of largest size. An *independent set* of $G$ is an empty subgraph of $G$. A *maximal* (*maximum*) *independent set* is defined is the same way as a maximal (maximum) clique. Note that an independent set of size $k$ in the graph $G$ is a clique of size $k$ in the complement graph of $G$. The clique and independent set functions presented below are implemented using one of two algorithms, called here *BranchAndBound* and *Dynamic*. The algorithms *BranchAndBound* and *Dynamic* are briefly described here. *BranchAndBound* : The algorithm is an implementation of the branch and bound algorithm by Bron and Kerbosch {cite:p}`BronKerb73`. The algorithm is designed to find maximal cliques and it has been adapted here to also find cliques of specific size which may not be maximal. It attempts to build a maximal clique by trying to expend the current maximal clique. Some heuristics are built into the algorithm which enable to prune the search tree. *Dynamic* : The algorithm finds a clique of size exactly $k$, not necessarily maximal, in the graph $G$ by using recursion and dynamic programming. If a clique of size $k$ exists in $G$, then, for a given vertex $v$ of $G$, there is either a clique of size $k\!-\!1$ in the subgraph induced by the neighbours of $v$, or there is a clique of size $k$ in the graph $G\!-\!v$. This is the recursive step. The *Dynamic* algorithm applies a different strategy (sorting of vertices and selection of vertices to consider) according to the order and density of the subgraph considered at the current level of recursion. This is achieved by dynamic programming, hence the name. This algorithm is due to Wendy Myrvold {cite:p}`Myrv`. **Comment** : When comparing both algorithms in the situation where the problem is to find a maximum clique one observes that in general *BranchAndBound* does better. However *Dynamic* outperforms *BranchAndBound* when the graphs under consideration are large (more then 400 vertices) random graphs with high density (larger than 0.5%). So far, it can only be said that the comparative behaviour of both algorithms is highly dependent on the structure of the graphs. --- :::{magma:function} HasClique(G, k) :input_types: GrphUnd, RngIntElt :output_types: BoolElt, {GrphVert} :label: HasClique_Grph_RingIntElt Returns `true` if and only if the graph $G$ has a maximal clique of size $k$. If `true`, returns such a clique as the second argument. ::: ```{function} HasClique(G, k, m : parameters) :input_types: GrphUnd, RngIntElt, BoolElt :output_types: BoolElt, {GrphVert} :label: HasClique_Grph_RingIntElt_BoolElt :parameters: Al : MonStgElt : "BranchAndBound" If $m$ is `true`, the function is `true` if and only if the graph $G$ has a maximal clique of size $k$. If $m$ is `false`, the function is `true` if and only if the graph $G$ has a --- not necessarily maximal --- clique of size $k$. If the function is `true`, an appropriate clique is returned as the second argument. When $m$ is `false`, the parameter `Al` enables the user to select the algorithm which is to be used. When $m$ is `true`, the parameter `Al` is ignored. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "BranchAndBound"` or `Al := "Dynamic"`. See the description given at the beginning of this section. The default is `"BranchAndBound"`. ``` :::{magma:function} HasClique(G, k, m, f : parameters) :input_types: GrphUnd, RngIntElt, BoolElt, RngIntElt :output_types: BoolElt, {GrphVert} :label: HasClique_Grph_RngIntElt_BoolElt_Rng_Int_Elt :parameters: Al : MonStgElt : "BranchAndBound" If $m$ is `true` and $f=0$, the function is `true` if and only if the graph $G$ has a maximal clique of size $k$. If $m$ is `true` and $f=1$, the function is `true` if and only if the graph $G$ has a maximal clique of size larger than or equal to $k$. If $m$ is `true` and $f=-1$, the function is `true` if and only if the graph $G$ has a maximal clique of size smaller than or equal to $k$. If $m$ is `false`, the function is `true` if and only if the graph $G$ has a --- not necessarily maximal --- clique of size $k$. If the function is `true`, an appropriate clique is returned as the second argument. When $m$ is `false`, the parameter `Al` enables the user to select the algorithm which is to be used. When $m$ is `true` the parameter `Al` is ignored, and when $m$ is `false`, the flag $f$ is ignored. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "BranchAndBound"` or `Al := "Dynamic"`. See the description given at the beginning of this section. The default is `"BranchAndBound"`. ::: :::{magma:function} MaximumClique(G : parameters) :input_types: GrphUnd :output_types: {GrphVert} :label: MaximumClique_Grph :parameters: Al : MonStgElt : "BranchAndBound" Finds a maximum clique in the graph $G$. The clique is returned as a set of vertices. The parameter `Al` enables the user to select the algorithm which is to be used. For a description of the algorithm used when `Al := "BranchAndBound"` see the beginning of this section. When `Al := "Dynamic"`, two steps are required. Step 1 : Finding a lowerbound on the size of a maximum clique. This is achieved by using the *dsatur* colouring (*dsatur* stands for saturation degree) due to Br\'elaz {cite:t}`Brel79`. The *dsatur* colouring gives a reasonably good approximation to the size of a maximum clique, usually with a penalty of $2$ to $3$. Step 2 : Assume that the lowerbound found in Step 1 if $l$. Then a maximum clique is found by finding the largest possible clique of size $k\geq l$ using the Dynamic algorithm. The default is `"BranchAndBound"`. ::: :::{magma:function} CliqueNumber(G : parameters) :input_types: GrphUnd :output_types: RngIntElt :label: CliqueNumber_Grph :parameters: Al : MonStgElt : "BranchAndBound" Finds the size of a maximum clique in the graph $G$. The parameter `Al` enables the user to select the algorithm which is to be used. For a description of the algorithm used when `Al := "BranchAndBound"` see the beginning of this section. For a description of the algorithm used when `Al := "Dynamic"` see the function {magma:function}`MaximumClique`. The default is `"BranchAndBound"`. ::: :::{magma:function} AllCliques(G : parameters) :input_types: GrphUnd :output_types: SeqEnum :label: AllCliques_Grph :parameters: Limit : RngIntElt : 0 Returns all maximal cliques of the graph $G$ as a sequence of sets of vertices. If `Limit`is set to a positive integer, returns `Limit`maximal cliques of $G$. ::: :::{magma:function} AllCliques(G, k : parameters) :input_types: GrphUnd, RngIntElt :output_types: SeqEnum :label: AllCliques_Grph_RngIntElt :parameters: Limit : RngIntElt : 0 Returns all maximal cliques of size $k$ of the graph $G$ as a sequence of sets of vertices. If `Limit`is set to a positive integer, returns `Limit`maximal cliques of size $k$ of $G$. ::: :::{magma:function} AllCliques(G, k, m : parameters) :input_types: GrphUnd, RngIntElt, BoolElt :output_types: SeqEnum :label: AllCliques_Grph_RngIntElt_BoolElt :parameters: Limit : RngIntElt : 0; Al : MonStgElt : "BranchAndBound" If $m$ is `true`, returns all maximal cliques of size $k$ in the graph $G$. If $m$ is `false`, returns all --- not necessarily maximal --- cliques of size $k$. When $m$ is `false`, the parameter `Al`enables the user to select the algorithm which is to be used. When $m$ is `true`, the parameter `Al` is ignored. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "BranchAndBound"` or `Al := "Dynamic"`. See the description given at the beginning of this section. The default is `"BranchAndBound"`. Except in the case where $m$ is `false` and `Al` is `"Dynamic"`, the parameter `Limit`, if set to a positive integer, limits the number of cliques returned. ::: Maximal independent sets or independent sets of a given size $k$ in a graph $G$ can be easily found by finding maximal cliques or cliques of size $k$ in the complement of $G$. Only two functions which are concerned with independent sets are provided: one finds a maximum independent set and the other returns the independence number of a graph. :::{magma:function} MaximumIndependentSet(G: parameters) :input_types: GrphUnd :output_types: {GrphVert} :label: MaximumIndependentSet_Grph :parameters: Al : MonStgElt : "BranchAndBound" Finds a maximum independent set in the graph $G$. The maximum independent set is returned as a set of vertices. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "BranchAndBound"` or `Al := "Dynamic"`. See the function {magma:function}`MaximumClique`. The default is `"BranchAndBound"`. ::: :::{magma:function} IndependenceNumber(G: parameters) :input_types: GrphUnd :output_types: RngIntElt :label: IndependenceNumber_Grph :parameters: Al : MonStgElt : "BranchAndBound" Finds the size of a maximum independent set in the graph $G$. The parameter `Al` enables the user to select the algorithm which is to be used: `Al := "BranchAndBound"` or `Al := "Dynamic"`. See the function {magma:function}`CliqueNumber`. The default is `"BranchAndBound"`. --> ::: :::{magma:example} Example: Cliques :label: Example_Cliques We illustrate the use of the clique functions with the following graph: ```magma > G := Graph< 9 | [ {4,5,6,7,8,9}, {4,5,6,7,8,9}, {4,5,6,7,8,9}, > {1,2,3,7,8,9}, {1,2,3,7,8,9}, {1,2,3,7,8,9}, > {1,2,3,4,5,6}, {1,2,3,4,5,6}, {1,2,3,4,5,6} ]>; > HasClique(G, 2); false %%a> assert not $1; > HasClique(G, 2, true); false %%a> assert not $1; > HasClique(G, 2, false); true { 1, 4 } > HasClique(G, 2, true: Al := "Dynamic"); false %%a> assert not $1; > HasClique(G, 2, false: Al := "Dynamic"); true { 1, 9 } > HasClique(G, 2, true, 1); true { 1, 4, 7 } > MaximumClique(G); { 1, 4, 7 } > AC := AllCliques(G); > #AC; 27 %%a> assert $1 eq 27; > AC3 := AllCliques(G,3); > #AC3; 27 %%a> assert $1 eq 27; > AC eq AC3; true %%a> assert $1; > AllCliques(G, 2, true); [] > AllCliques(G, 2, false); [ \ { 1, 4 }, \ { 1, 5 }, \ { 1, 6 }, \ { 1, 7 }, \ { 1, 8 }, \ { 1, 9 }, \ { 2, 4 }, \ { 2, 5 }, \ { 2, 6 }, \ { 2, 7 }, \ { 2, 8 }, \ { 2, 9 }, \ { 3, 4 }, \ { 3, 5 }, \ { 3, 6 }, \ { 3, 7 }, \ { 3, 8 }, \ { 3, 9 }, \ { 4, 7 }, \ { 4, 8 }, \ { 4, 9 }, \ { 5, 7 }, \ { 5, 8 }, \ { 5, 9 }, \ { 6, 7 }, \ { 6, 8 }, \ { 6, 9 } ] ``` :::