## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
The graphgen program was downloaded from the SNAP web site and modified to use a random seed so that generated graphs with the same parameters were actually different. This allows us to generate a variety of graphs, such as complete graphs, star graphs, 2D grid graphs, Erdos-Renyi random graphs with an exact number of edges, k-regular graphs (each vertex with degree k), Albert-Barbasi graphs, power law graphs, Klienberg copying model graphs and small-world graphs. Finding maximum cliques in a complete graph, star graph and 2D grid graph is trivial. Similarly, and surprisingly, small scale experiments suggested that Albert-Barbasi and Klienberg's graphs are also easy with respect to maximum clique. However k-regular and small world are a challenge. \begin{table}
\begin{tabular}{|c c|c c c|c c c|c c c|} \hline \multicolumn{2}{|c|}{**instance**} & \multicolumn{4}{c|}{**nodes**} & \multicolumn{4}{c|}{**MCSa**} & \multicolumn{4}{c|}{**BBMC**} \\
**n** & **p** & \(\mathbf{s_{1}}\) & \(\mathbf{s_{2}}\) & \(\mathbf{s_{3}}\) & \(\mathbf{s_{1}}\) & \(\mathbf{s_{2}}\) & \(\mathbf{s_{3}}\) & \(\mathbf{s_{1}}\) & \(\mathbf{s_{2}}\) & \(\mathbf{s_{3}}\) \\ \hline
1,000 & 0.1 & 4,536 & **4,472** & 4,563 & 0 & 0 & 0 & 0 & 0 & 0 \\  & 0.2 & 39,478 & **38,250** & 38,838 & 0 & 0 & 0 & 0 & 0 & 0 \\  & 0.3 & 400,018 & **371,360** & 404,948 & 4 & 4 & 4 & 2 & 2 & 2 \\  & 0.4 & 3,936,761 & **3,780,737** & 4,052,677 & 40 & 39 & 38 & 26 & 25 & 26 \\  & 0.5 & 79,603,712 & **75,555,478** & 80,018,645 & 860 & 910 & 859 & 570 & 574 & 604 \\
3,000 & 0.1 & 144,375 & **142,719** & 145,487 & 3 & 3 & 3 & 2 & 2 & 2 \\  & 0.2 & 2,802,011 & **2,723,443** & 2,804,830 & 38 & 38 & 38 & 32 & 32 & 32 \\  & 0.3 & 73,086,978 & **71,653,889** & 73,354,584 & 964 & 960 & 978 & 926 & 930 & 931 \\
10,000 & 0.1 & 5,351,591 & **5,303,615** & 5,432,812 & 236 & 252 & 245 & 212 & 216 & 214 \\
15,000 & 0.1 & 22,077,212 & 21,751,100 & **21,694,036** & 1,179 & 1,117 & 1,081 & 1,249 & 1,235 & 1,208 \\ \hline \end{tabular}
\end{table} 
Table 6: Large random graphs, sample size 10. Figure 9: k-Regular SNAP instances \(KR(200,k)\), \(130\leq k\leq 160\), sample size 20. The SNAP graphgen program was used to generated k-regular graphs \(KR(n,k)\), _i.e._, random graphs with \(n\) vertices each with degree \(k\). Graphs were generated with \(n=200\) and \(50\leq k\leq 160\), with \(k\) varying in steps of 5, 20 instances at each point. BBMC1 and BBMC2 were then applied to each instance. Obviously, with style equal to 1 or 3, there is no heuristic information to be exploited at the top of search. But would a minimum width ordering, style 2, have an advantage? Figure 9 shows average search effort in nodes plotted against uniform degree \(k\). We see that minimum width ordering does indeed have an advantage. What is also of interest is that \(KR(n,k)\) instances tend to be harder than their \(G(n,p)\) equivalents. For example, we can compare \(KR(200,160)\) with \(G(200,0.8)\) in Figure 6: MCSa1 took on average 1.9 million nodes for \(G(200,0.8)\) and BBMC1 took on average 4.7 million nodes on the twenty \(KR(200,160)\) instances. Small-World graphs \(SW(n,k,p)\) were then generated using graphgen. This takes three parameters: \(n\) the number of vertices, \(k\) where each vertex is connected to \(k\) nearest neighbours to the right in a ring topology (_i.e._, vertices start with uniform degree \(2k\)), and \(p\) a rewiring probability. This corresponds to the graphs in Figure 1 of [32]. Small-World graphs were generated with \(n=1,000\), \(50\leq k\leq 100\) in steps of 5, \(0.0\leq p\leq 0.25\) in steps of 0.01, 10 graphs at each point. BBMC1 was then applied

Figure 10: Small world graphs \(SW(200,k,p)\): (upper) search effort, (lower) maximum clique size. to each instance to investigate how difficulty of finding a maximum clique varies with respect to \(k\) and \(p\) and also how size of maximum clique varies, _i.e._, this is an investigation of the problem.