## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
When \(Q\) is exhausted (line 57) the outer while loop (line 54) starts a new colour class (lines 55 to 64). ```
49 voidBBColour(BitSetP,int[]U,int[]colour){
51 BitSetcopyP =(BitSet)P.clone();
52 intcolourClass = 0;
53 inti=0;
54 while(copyP.cardinality()!=0){
55 colourClass++;
56 BitSetQ =(BitSet)copyP.clone();
57 while(Q.cardinality()!=0){
58 intv=Q.nextSetBit(0);
59 copyP.set(v,false);
60Q.set(v,false);
61Q.and(invN[v]);
62U[i]=v;
63 colour[i++]=colourClass;
64}
65}
66}
67}
```

Listing 12 shows how the candidate BitSet is renamed/reordered. In fact it is not the candidate BitSet that is reordered, rather it is the description of the neighbourhood \(N\) and its inverse \(invN\) that is reordered. Again, as in MCQ and MCSa, a Veretx array is created (lines 69 to 73) and is sorted into one of three possible orders (lines 74 to 76). Once sorted, a bit in position \(i\) of the candidate BitSet \(P\) corresponds to the integer vertex \(v=V[i].index\). The neighbourhood and its inverse are then reordered in the loop of lines 77 to 83. For all pairs \((i,j)\), we select the corresponding vertices \(u\) and \(v\) from \(V\) (lines 79 and 80) and if they are adjacent then the \(j^{th}\) bit of \(N[i]\) is set true, otherwise false (line 81). Similarly, the inverse neighbourhood is updated in line 82. The loop could be made twice as fast by exploiting symmetries in the adjacency matrix \(A\). In any event, this method is called once at the top of search and is generally an insignificant contribution to run time. ```
voidorderVertices(){ for(inti=0;i<n;i++){ V[i]=newVertex(i,degree[i]); for(intj=0;j<n;j++) if(A[i|j]==1)V[i].nebDeg=V[i].nebDeg+degree[j]; } if(style==1)Arrays.sort(V); if(style==2)minWidthOrder(V); if(style==3)Arrays.sort(V,newMCRComparator()); for(inti=0;i<n;i++) for(intj=0;j<n;j++){ intu=V[i].index; intv[j].index; N[i].set(j,A[u][v]==1); invN[i].set(j,A[u][v]==0); } }
84}
85 voidsaveSolution(BitSetC){ Arrays.fill(solution,0); for(inti=0;i<C.size();i++)if(C.get(i))solution[V[i].index]=1; maxSize=C.cardinality();
90} }
```

Listing 12: San Segundo's BB-MaxClique in Java (part 2). BBMC requires its own \(saveSolution\) method (lines 86 to 90 of Listing 12) due to \(C\) being a BitSet. Again the solution is saved into the integer array \(solution\) and again we need to use the Vertex array \(V\) to map bits to vertices. This is done in line 88: If the \(i^{th}\) bit of \(C\) is true then integer vertex \(V[i].index\) is in the solution. This explains why \(V\) is global to the \(BBMC\) class. #### 2.4.2 Observations on BBMC

In our Java implementation, we might expect a speedup if we did away with the in-built BitSet and did our own bit-string manipulations explicitly. It is also worth noting that in [10] comparisons are made with [PERSON]'s results in [13] by rescaling tabulated results, _i.e._, [PERSON]'s code was not actually run, but this is not unusual. ### Summary of MCQ, MCR, MCS and BBMC

Putting aside the chronology [11; 12; 13; 15], MCSa is the most general algorithm presented here. BBMC is in essence MCSa with a BitSet encoding of sets. MCQ is MCSa except that we do away with the static colour ordering and allow MCQ to colour and sort the candidate set using the candidate set, somewhat in the manner of Uroborus the serpent that eats itself. And MCSb is MCSa with an additional colour repair step. ## 3 Exact Algorithms for Maximum Clique: A Brief History

We now present a brief history of complete algorithms for the maximum clique problems, starting from 1990. The algorithms are presented in chronological order. **1990:** In 1990 [3] [PERSON] and [PERSON] present a branch and bound algorithm. Vertices are ordered in non-decreasing degree order at each depth in the binomial search with a cut-off based on the size of the largest clique found so far. Their algorithm is presented in Fortran 77 along with code to generate random graphs; consequently, their empirical results are entirely reproducible.