## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Bbmc
#### 2.4.1 BBMC in Java
For each algorithm we have three columns, one for each _style_: First column \(s_{1}\) is style 1 with vertices in non-increasing degree order, \(s_{2}\) is style 2 with vertices in minimum width order, \(s_{3}\) is style 3 with vertices in non-increasing degree order tie-breaking on sum of neighbouring degrees. Table 4 gives the number of nodes, in millions, for the experiments in Table 3. In Table 3 a **bold** entry is the best run time for that algorithm against the problem instance, and this is done only when run times

\begin{table}
\begin{tabular}{|l|c c c|c c c|c c c|c c c|} \hline  & \multicolumn{3}{c|}{**MCQ**} & \multicolumn{3}{c|}{**MCSa**} & \multicolumn{3}{c|}{**MCSb**} & \multicolumn{3}{c|}{**BBMC**} \\

differ significantly. For MCQ there is no particular style that is a consistent winner. This is a surprise as MCQ3 is [PERSON]'s MCR and in [15] it is claimed that MCR was faster than MCQ. The evidence that supports this claim is Table 2 of [15], 8 of the 66 DIMACS instances. For MCSa and BBMC style 2 is best more often than not, and in MCSb style 1 is best more often than not. Overall we see that the BBMC2 is our best algorithm, _i.e._, BBMC with a minimum width ordering. ### More Benchmarks (not DIMACS)

In [16] experiments are performed on counting maximal cliques in exceptionally large sparse graphs, such as the Pajek data sets (graphs with hundreds of thousands of vertices) and SNAP data sets (graphs with vertices in the millions) [35]. Those graphs are out of the reach of the exact algorithms reported here. The initial reason for this is space consumption. To tackle such large sparse problems, we require a change of representation, away from the adjacency matrix and towards the adjacency lists as used in [16]. Therefore we explore large random instances as in [11; 13] to further investigate ordering and the effect of the BitSet representation, the hard solvable instances in BHOSLIB to see how far we can go, and structured graphs produced via the SNAP (Stanford Network Analysis Project) graph generator. We start with BHOSLIB. In Table 5 we have the only instances from the BHOSLIB suite (Benchmarks with Hidden Optimum Solutions [36]) that could be solved in 4 hours. Each instance has a maximum clique of size 30. A **bold** entry is the best run time. For this suite, we see that with respect to style there is no clear winner. Table 6 shows results on large random problems. Similar experiments are reported in Tables 4 and 5 of [11] and Table 2 in [13]. The first three columns are the nodes visited, and this is the same for MCSa and BBMC. Run times are then given in seconds for MCSa and BBMC using each of the three styles. Highlighted in **bold** is the search of fewest nodes and this is style 2 (minimum width ordering) in all but one case. Comparing the run times, we see that as problems get larger, involving more vertices, the relative speed difference between BBMC and MCSa diminishes, and at \(n=15,000\) the performances of MCSa and BBMC are essentially the same. This was also observed in [10] and is expected: As problems get larger the BitSet requires more words to represent the set, and with more words the number of iterations within the BitSet increases. \begin{table}
\begin{tabular}{|l|c|c|c c|c c|c c|} \hline
**instance** & **n** & **edges** & \multicolumn{2}{c|}{**BBMC1**} & \multicolumn{2}{c|}{**BBMC2**} & \multicolumn{2}{c|}{**BBMC3**} \\ \hline frb30-15-1 & 450 & 83,198 & 292,095 & **3,099** & 626,833 & 6,503 & 361,949 & 3,951 \\ frb30-15-2 & 450 & 83,151 & 557,252 & 5,404 & 599,543 & 6,136 & 436,110 & **4,490** \\ frb30-15-3 & 450 & 83,126 & 167,116 & 1,707 & 265,157 & 2,700 & 118,495 & **1,309** \\ frb30-15-4 & 450 & 83,194 & 991,460 & 9,663 & 861,391 & **8,513** & 1,028,129 & 9,781 \\ frb30-15-5 & 450 & 83,231 & 282,763 & 2,845 & 674,987 & 7,033 & 281,152 & **2,802** \\ \hline \end{tabular}
\end{table} 
Table 5: BHOSLIB using BBMC: 1,000’s of nodes and run time in seconds. Problems have 450 vertices and graph density 0.82.