# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 3 Minor Improvements in HTS2
If the size of the neighborhood \(N(C)\) of the current clique satisfies \(|N(C)|<\lambda_{2}\), then the generation of the clique by the main heuristic is completed by applying the exact algorithm to \(N(C)\). If the clique generated has at least \(\theta\) vertices, the algorithm reverts to a somewhat larger stored neighborhood with less than \(\lambda_{1}\) vertices and applies the exact algorithm. In HTS2, the two \(\lambda\) parameters are determined by the edge density \(2|E|/(|V|(|V|-1))\), as shown in Table 4. The parameter \(\lambda_{2}\) is also used in the protection mechanism within tabu search to avoid applying the exact algorithm to excessively large subproblems. The value of the tabu tenure _Tstenure_ is not at all critical for HTS2. Values of 6, 12, and 20 were used, and all proved successful. The tabu search parameter _Tssetmin_ is the critical parameter to be set by the user. It must be less than \(\theta\), but, if it is too small, attempts may be made to solve exactly subproblems that are too large, requiring the protection mechanism. Otherwise, larger values make tabu search faster, but smaller values may make tabu search more powerful. A balance should be achieved. It should be noted that the current implementation allows the original \(\theta\) and \(\lambda\) parameters from HTS to override these choices if the user requires it. Otherwise, _Tstenure_ and _Tssetmin_ are the only relevant parameters in HTS2. ## 5 Comparison of HTS, HTS2, and SBTS

This section presents a comparison of the original HTS algorithm, the new HTS2 algorithm, and SBTS. The software for the SBTS algorithm is available online as [17]. The benchmarks selected are BHOSLIB instances [18], some of the harder DIMACS instances [16], Sloane code construction instances [6], and permutation code construction instances from [7]. A few instances shown in [2] to be most easily solved using a pre-processing method are excluded, so the description of pre-processing need not be repeated here. These benchmarks are not ideal in the sense that the optimal solution is known for many of them, but they are at least easily available to allow comparison by others. Using an exact algorithm cannot be expected to be the fastest algorithm, but the more thorough local search might lead to improved solutions if improved solutions are possible. Of particular interest, then, is the permutation code instance 7_5. The vertices correspond to the permutations on 7 symbols, excluding those permutations at Hamming distance 1, 2, 3, or 4 from the identity permutation. Two vertices are adjacent if they are at Hamming distance \(\geq\)5. A theoretical construction using group theory shows that there exists a clique with 78 vertices [19], but the largest clique found with a maximum clique algorithm previously has 72 vertices (or 73 using the pre-processing method in [2]). For permutation code instances other than 7_4 and 7_5, the vertices of the graph correspond to orbits of permutations under a group, as explained in [7]. The processor used for the experiments was an Intel(R) Core(TM) i3-9100 3.60 GHz processor with 4 GB of RAM. In most cases, the parameters used for HTS were the same as given in [2], the parameters for _Tstenure_ and _Tssetmin_ in HTS2 were the same as used for these parameters in HTS in [2], and the \begin{table}
\begin{tabular}{l l l l l} \hline \hline
1 & \(\geq\) edge density & \(\geq\) 0.95 & \(\lambda_{1}=\) 80 & \(\lambda_{2}=\) 60 \\
0.95 & \(>\) edge density & \(\geq\) 0.9 & \(\lambda_{1}=\) 100 & \(\lambda_{2}=\) 80 \\
0.9 & \(>\) edge density & \(\geq\) 0.84 & \(\lambda_{1}=\) 140 & \(\lambda_{2}=\) 120 \\
0.84 & \(>\) edge density & \(\geq\) 0.74 & \(\lambda_{1}=\) 160 & \(\lambda_{2}=\) 140 \\
0.74 & \(>\) edge density & & \(\lambda_{1}=\) 180 & \(\lambda_{2}=\) 160 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Choices of parameters \(\lambda_{1}\) and \(\lambda_{2}\). default setting for tabu tenure was used in SBTS.