## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
The top row has \(n=100\), middle row \(n=150\) and bottom row \(n=200\). For MCQ1 the sample size at \(G(200,0.95)\) was reduced to 28, _i.e._, the MCQ1-200 job was terminated after 60 hours. As we apply the modifications to MCQ, we see a reduction in nodes with MCSb1 exploring less states than MCSa1 and MCSa1 less than MCQ1. However, on the right we see that reduction in search space does not always result in reduction in run time. MCSb1 is always slower than MCSa1, _i.e._, the colour repair is too expensive and when \(n=100\) MCSb1 is often more expensive to run than MCQ! Therefore, it appears that MCS gets its advantage just from the static colour ordering and that the colour repair slows it down. Figure 6: \(G(n,p)\), sample size 100. MCQ _vs._ MCS, where is the win? (left) Search effort in nodes visited (_i.e._, decisions made by the search process); (right) run time in milliseconds. We also see a region where problems are hard for all our algorithms, at \(n=100\) and \(n=150\), both in terms of nodes and run time, and in [10] it is suggested that this behaviour is a \"... phase transition to triviality...\". However at \(n=200\) there is a different picture. We see a hard region in terms of nodes but an ever-increasing run time. That is, even though nodes are falling, CPU time is climbing. This agrees with the tabulated results in [11] (Tables 4 and 5 on page 580) for BB-MaxClique. It is a conjecture that run time increases because the cost of each node (call to expand) incurs more cost in the colouring of

\begin{table}
\begin{tabular}{|c|r r r r|r r r|r r r|} \hline
**instance** & \multicolumn{2}{c|}{**MCQ1**} & \multicolumn{2}{c|}{**MCSa1**} & \multicolumn{2}{c|}{**MCSb1**} & \multicolumn{2}{c|}{**} \\ \hline brock200-1 & 868,213 & 7 & (21) & 524,723 & 4 & (21) & 245,146 & **3** & (21) \\ brock400-1 & 342,473,950 & 4,471 & (27) & 198,359,829 & 2,888 & (27) & 142,253,319 & **2,551** & (27) \\ brock400-2 & 224,839,070 & 2,923 & (29) & 145,597,994 & 2,089 & (29) & 61,327,056 & **1,199** & (29) \\ brock400-3 & 194,403,055 & 2,322 & (31) & 120,230,513 & 1,616 & (31) & 70,263,846 & **1,234** & (31) \\ brock400-4 & 82,056,086 & 1,117 & (33) & 54,440,888 & **802** & (33) & 68,252,352 & 1,209 & (33) \\ brock800-1 & 1,247,519,247 & — & **(23)** & 1,055,945,239 & — & **(23)** & 911,465,283 & — & (21) \\ brock800-2 & 1,387,973,191 & — & (21) & 1,171,057,646 & — & **(24)** & 914,638,570 & — & (21) \\ brock800-3 & 1,332,309,827 & — & (21) & 1,159,165,900 & — & (21) & 914,235,793 & — & (21) \\ brock800-4 & 804,901,115 & — & (26) & 640,444,536 & **12,568** & (26) & 659,145,642 & 13,924 & (26) \\ hamming10-4 & 636,203,658 & — & **(40)** & 950,939,457 & — & (37) & 858,347,653 & — & (37) \\ johnson32-2-4 & 10,447,210,976 & — & (16) & 8,269,639,389 & — & (16) & 7,345,343,221 & — & (16) \\ keller5 & 603,233,453 & — & (27) & 596,150,386 & — & (27) & 523,346,613 & — & (27) \\ keller6 & 285,704,599 & — & (48) & 226,330,037 & — & (52) & 240,958,450 & — & **(54)** \\ MANN-a27 & 38,019 & 9 & (126) & 38,019 & **6** & (126) & 38,597 & 8 & (126) \\ MANN-a45 & 2,851,572 & 4,989 & (345) & 2,851,572 & **3,766** & (345) & 2,545,131 &



the relatively larger candidate set. In going from \(G(200,0.90)\) to \(G(200,0.95)\), the maximum clique size increased on average from 41 to 62, a 50% increase, and for MCSa1 the average number of nodes fell by 20% (30% for MCSb1). The search space has fallen and the clique size has increased, which increases the cost of colouring and results in an overall increase in run time. Therefore it does not appear to be a phase transition in the sense of [28, 29, 30], _i.e._, a feature of the problem that is algorithm independent. We now report on the 66 DIMACS instances [31] in Table 1. For each algorithm, we have 3 entries: The number of nodes, CPU time in seconds, and in brackets the size of the largest clique found. Each algorithm was allowed 14,400 CPU seconds and if that was exceeded we have a table entry of \"--\".