## 2 Algorithms for the Maximum Clique Problem
```
1 colourOrder:: (graph \(G\), set \(P\)) \(\rightarrow\) (array of integer, array of integer)
2 begin
3\(colour\leftarrow\) an array of integer
4\(order\leftarrow\) an array of integer
5\(P^{\prime}\gets P\)// set of uncoloured vertices
6\(k\gets 1\)// current colour
7 while\(P^{\prime}\
eq\emptyset\)do
8\(Q\gets P^{\prime}\)// vertices to consider for the current colour
9 while\(Q\
eq\emptyset\)do
10\(v\leftarrow\) the first element of \(Q\)// get next vertex to colour
11\(P^{\prime}\gets P^{\prime}\setminus\{v\}\)
12\(Q\gets Q\setminus\{v\}\)
13 append \(k\) to \(colour\)
14 append \(v\) to \(order\)
15\(Q\gets Q\cap\overline{\mathrm{N}(G,v)}\)// remove adjacent vertices
16\(k\gets k+1\)// start a new colour
17 return\((colour,order)\)
```  
**Algorithm 1**Sequentially colour vertices and sort into non-decreasing colour order. Figure 1: A small graph, together with a constructive colouring. We may now discuss Algorithm 2, our baseline sequential algorithm. Following [PERSON] [12], we opt to order vertices in a non-increasing degree order at the top of the search, use a static ordering throughout, use a bitset encoding and do not include a colour repair mechanism--thus, our algorithm is a bitset encoded version of MCSa1 (although the techniques presented are not sensitive to this choice). ```
1 maxClique :: (graph \(G\)) \(\rightarrow\) set of integer
2 begin
3\(C_{max}\leftarrow\emptyset\)
4 permute \(G\), so that the vertices are in non-increasing degree order
5 expand\((G,\emptyset,\textsc{V}(G),C_{max})\)
6 return\(C_{max}\) (unpermuted)
7 expand :: (graph \(G\), set \(C\), set \(P\), set \(C_{max}\))
8 begin
9\((colour,order)\leftarrow\texttt{colourOrder}(G,P)\)
10 for\(i\leftarrow|P|\) downto \(1\)do
11 if\(|C|+colour[i]>|C_{max}|\)then
12\(v\gets order[i]\)
13\(C\gets C\cup\{v\}\)
14\(P^{\prime}\gets P\cap\textsc{N}(G,v)\)
15 if\(P^{\prime}=\emptyset\)then
16 if\(|C|>|C_{max}|\)then\(C_{max}\gets C\)
17 elseexpand\((G,C,P^{\prime},C_{max})\)
18\(C\gets C\setminus\{v\}\)
19\(P\gets P\setminus\{v\}\)
```  
**Algorithm 2**An exact algorithm to deliver a maximum clique. Procedure maxClique permutes the graph, such that the vertices are in non-increasing degree order (and this order is exploited by the sequential colouring), then calls the recursive search procedure, expand, on the graph, \(G\), with an initially empty growing clique and a full candidate set. Procedure expand (lines 7 to 19) searches for cliques. First, the vertices in the candidate set, \(P\), are coloured and sorted (line 9). The procedure then iterates from highest to lowest coloured vertex (line 10). If the size of the growing clique plus the colour number of the current vertex is sufficient to potentially unseat the incumbent, the search progresses (line 11). The \(i\)th vertex \(v\), ordered by colour, is selected and added to the growing clique (lines 12 and 13). A new candidate set, \(P^{\prime}\), is created, where \(P^{\prime}\) is the set of vertices in \(P\) adjacent to \(v\). If \(C\) cannot grow any further (line 15) and is larger than the incumbent, it is saved (line 16). Otherwise, the search proceeds via a recursive call, with the enlarged clique, \(C\), and reduced candidate set \(P^{\prime}\) (line 17). Regardless, having explored the option of taking vertex \(v\) (lines 12 to 17), the search then explores the option of not taking vertex \(v\) (lines 18 and 19, then iterating back to line 10). Note that sets are encoded as bit strings, i.e., a bitset encoding similar to San Segundo's BBMC[10] is used. This allows the implementation to exploit bit parallelism. The graph should be encoded as an array of \(n\) bitsets (this encoding may be done when the graph is permuted). Thus, the call, \(\mathrm{N}(G,v)\), in line 14 of Algorithm 2 delivers the \(v\)th adjacency bitset, and similarly, line 15 of Algorithm 1 delivers the complement of the \(v\)th adjacency bitset. To add or remove a vertex from a set, a bit is flipped, and to take the intersection of two sets, a logical-and operation is performed.