# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 3 Minor Improvements in HTS2  
Apart from the change from the exact and pseudoexact search in HTS to the exact \"ordered local coloring\" algorithm detailed in Algorithm 1, there are some other relatively minor changes from HTS in HTS2. As well as the tabu search algorithm, HTS has a main heuristic that generates good starting solutions (sometimes finds the best solution itself) and \(i\)-optimizations for \(i=1,2,3\). These \(i\)-optimizations remove \(i\) vertices from the current clique in all possible ways and apply the exact algorithm to the neighbor set of vertices adjacent to all remaining vertices in an attempt to find a new larger clique. This continues until there is no improvement. In HTS, there are thresholds \(\theta_{1}\) \begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{**Instance**} & \multirow{2}{*}{**C\&P**} & \multirow{2}{*}{**C\&P with**} & \multirow{2}{*}{**C\&P with Ordered**} \\  & & & **Start \& Local** & **Ordered Local** & **DSatur Start** \\  & & & **Coloring** & **Coloring** & **and Ordered Local Coloring** \\ \hline C4000\_5 & 1659 & 1725 & 1795 & 1389 \\ C2000\_9 & 23 & 252 & 236 & 215 \\ keller6 & 260 & 225 & 285 & 329 \\ frb35-17-4 & 833 & 2359 & 2827 & 1660 \\ frb50-23-3 & 765 & 825 & 996 & 784 \\ frb50-23-2 & 763 & 796 & 948 & 731 \\ 7\_5 & 79 & 98 & 96 & 94 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Evaluation of the mean number of tabu search iterations per second for four of the algorithms appearing in Tables 1 and 2. These replace exact search and pseudoexact search in Hybrid Tabu Search (HTS). The best exact algorithm should maximize the number of tabu search iterations per second during an extended run. \(\theta_{2}\), \(\theta_{3}\), \(\theta_{\text{ts}}\) for the four optimizations. In HTS, these thresholds are allowed to be different and are selected so that each optimization is only applied to very promising cases, and 3-optimization never makes HTS unacceptably slow. In HTS2, these four thresholds are replaced by a single threshold \(\theta\). The justification for this is that the improved performance of the tabu search makes a different threshold for tabu search unnecessary, and the relative slowness of 3-optimization in some instances can be dealt with by considering the size of the current clique. Thus, the overall structure of HTS2 is as shown in Algorithm 2. ```
1:\(BestC:=\emptyset\);
2:\(k:=0\);
3:while\(runtime\leq max\_runtime\)do
4:\(k:=k+1\);
5:\(C:=Main\_heuristic(k)\);
6:if\(|C|\geq\theta\)then
7:\(1\_optimize(C)\);
8:\(C:=ts\_optimize(C)\);
9:if\(|C|\leq 200\)then
10:\(C:=3\_optimize(C)\);
11:else
12:\(C:=2\_optimize(C)\);
13:endif
14:endif
15:if\(|C|>|BestC|\)then
16:\(BestC:=C\);
17:endif
18:endwhile
```  
**Algorithm 2**Outline of the overall structure of the algorithm HTS2. For any current clique \(C\), \(N(C)\) denotes the set of vertices of \(V\) adjacent to all vertices in \(C\). In the main heuristic of the original HTS algorithm, a sequence \(S\) is selected. A variable _adjchoices_ cycles through the values in \(S\) and controls the choice of the next vertex in \(N(C)\) to add to the clique \(C\). A set \(U\) consists of all vertices of \(N(C)\) if \(|N(C)|\leq\)_adjchoices_, or _adjchoices_ randomly selected vertices of \(N(C)\) otherwise. A vertex \(u\) of \(U\) is chosen to add to \(C\) which gives the largest value of \(N(C\cup\{u\})\). The most common \(S\) in the experiments in [2] is \(S=[1,50,80,100,120,160,200,300,600,800]\), and \(S\) is fixed to this choice in HTS2 unless the graph has \(<1000\) vertices when \(S=[1,50,80,100,120,160,200,300]\). Thus, no decision on an appropriate \(S\) is necessary in HTS2. Pseudocode for the main heuristic is presented in Algorithm 3, and pseudocode for the i-optimizations is presented in Algorithm 4. In the original HTS algorithm a parameter, _Nontabu max_ is used in tabu search.