# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 2 Exact Algorithms with a Coloring Bound
### Evaluation of Exact Algorithms with a Coloring Bound for Use in HS2  
Although the results in Tables 1 and 2 give a useful comparison, it should be noticed that the subproblems to which exact and pseudoexact search is typically applied in HTS may be much smaller than the instances used in those tables. Thus, four of the algorithms were evaluated further by using them in place of the exact and pseudoexact search in HTS. The critical improvement in performance arises from maximizing the mean number of tabu search iterations per second, and this was calculated for an extended run on each of seven instances. These were DIMACS, BHOSLIB, and permutation code instances used in [2], and, in general, the same parameters were used for HTS as in the experiments in [2]. The results are shown in Table 3.  
It appears that there is much less difference in the results than in the previous tables, in part because if the time for exact search is small the time to calculate neighborhoods becomes more significant. However, it appears from further experiments that the third and fourth algorithms (using ordering) allow the parameter _Tssetmin_ in HTS (determining the smallest current clique from which vertices may be removed) to be smaller. These smaller values allow exact search to be applied to larger subproblems without excessively slowing tabu search and can improve performance as a result. From inspection of Table 3, the third algorithm \"C&P with ordered local coloring\" was selected for use in an improved version HTS2 of HTS. This algorithm also had the merit that it was simpler than the fourth algorithm. Pseudocode for \"C&P with ordered local coloring\" is shown in Algorithm 1.  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & & **C\&P** & **C\&P** & **C\&P** \\
**Instance** & **C\&P** & **Local** & **Start** & **Start and** \\  & & **Coloring** & **Coloring** & **Local Coloring** \\ \hline brock400\_2 & 30,904 & 6407 & 30,538 & 5842 \\ brock400\_4 & 15,260 & 1420 & 11,216 & 1332 \\ brock800\_2 & 191,613 & 74,696 & 183,831 & 73,537 \\ brock800\_4 & 127,564 & 37,835 & 113,604 & 37,599 \\ keller5 & unterminated & unterminated & unterminated & unterminated \\ p\_hat300-3 & 25,312 & 1110 & 11,884 & 960 \\ p\_hat700-2 & unterminated & 22,099 & unterminated & 20,523 \\ p\_hat1500-1 & 12 & 17 & 15 & 17 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Comparison of run times (in seconds) for four exact algorithms for the maximum clique problem.  
\begin{table}
\begin{tabular}{l c c c c} \hline \hline  & **C\&P** & **C\&P** & **C\&P with** & **C\&P with** \\
**Instance** & **with Ordered** & **Ordered Start** & **Ordered Saturation** & **Ordered DSatur** \\  & **Local** & **and Ordered** & **Start \& Ordered** & **Start \& Ordered** \\  & **Coloring** & **Local Coloring** & **Local Coloring** & **Local Coloring** \\ \hline brock400\_2 & 1246 & 1134 & 1044 & 1092 \\ brock400\_4 & 1467 & 282 & 287 & 252 \\ brock800\_2 & 22,121 & 24,626 & 24,466 & 26,148 \\ brock800\_4 & 10,938 & 15,228 & 13,038 & 12,761 \\ keller5 & 270,687 & 278,555 & 144,558 & 159,936 \\ p\_hat300-3 & 151 & 188 & 132 & 66 \\ p\_hat700-2 & 1721 & 1979 & 659 & 355 \\ p\_hat1500-1 & 11 & 11 & 12 & 12 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Comparison of run times (in seconds) for four improved exact algorithms for the maximum clique problem using ordering. The algorithms in the second and third columns are variations of those in columns 3 and 5 of Table 1 using ordering. The fourth and fifth columns are variations of the third column using saturation or DSatur (Degree of Saturation) start, respectively.