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 [Bron and Kerbosch, 1973].

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 [Myrvold et al., n.d.].

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.

---

HasClique(G, k): GrphUnd, RngIntElt → BoolElt, {GrphVert}

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.

HasClique(G, k, m : parameters): GrphUnd, RngIntElt, BoolElt → BoolElt, {GrphVert}

Al : MonStgElt                    Default: "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".

HasClique(G, k, m, f : parameters): GrphUnd, RngIntElt, BoolElt, RngIntElt → BoolElt, {GrphVert}

Al : MonStgElt                    Default: "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".

MaximumClique(G : parameters): GrphUnd → {GrphVert}

Al : MonStgElt                    Default: "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 Brelaz [1979].

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

CliqueNumber(G : parameters): GrphUnd → RngIntElt

Al : MonStgElt                    Default: "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 MaximumClique. The default is "BranchAndBound".

AllCliques(G : parameters): GrphUnd → SeqEnum

Limit : RngIntElt                    Default: 0

Returns all maximal cliques of the graph \(G\) as a sequence of sets of vertices. If Limitis set to a positive integer, returns Limitmaximal cliques of \(G\).

AllCliques(G, k : parameters): GrphUnd, RngIntElt → SeqEnum

Limit : RngIntElt                    Default: 0

Returns all maximal cliques of size \(k\) of the graph \(G\) as a sequence of sets of vertices. If Limitis set to a positive integer, returns Limitmaximal cliques of size \(k\) of \(G\).

AllCliques(G, k, m : parameters): GrphUnd, RngIntElt, BoolElt → SeqEnum

Al : MonStgElt                    Default: "BranchAndBound"

Limit : RngIntElt                    Default: 0

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

MaximumIndependentSet(G: parameters): GrphUnd → {GrphVert}

Al : MonStgElt                    Default: "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 MaximumClique. The default is "BranchAndBound".

IndependenceNumber(G: parameters): GrphUnd → RngIntElt

Al : MonStgElt                    Default: "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 CliqueNumber. The default is "BranchAndBound". –>

Example: Cliques

We illustrate the use of the clique functions with the following graph:

> 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 }
]