# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 3 Minor Improvements in HTS2
For 7_5, HTS2 found a clique with 75 vertices once and cliques with 74 vertices four times in 364,585 s, whereas SBTS found cliques with 72 vertices twice but could not improve this in 1,399,916.1 s. Similarly, for 8_5 cyclic, HTS2 found a clique with 49 vertices in 6799 s, whereas SBTS found cliques with 46 vertices four times but could not improve this in 61,097.2 s.

## 6 Conclusions

The replacement of the pseudoexact algorithm in HTS with an improved exact algorithm in HTS2 has allowed a pure comparison of tabu search using exact search with a more standard type of tabu search. The interest of the authors is in code construction problems, where certain instances only have to be solved once. The critical issue is that the largest clique possible is found, and run time is relatively unimportant. It is clear that SBTS is much faster than HTS2 for most instances and should be used in applications where clique problems have to be solved quickly. HTS2 has found the same size clique in all instances except 7_5 and 8_5 cyclic, where it has found larger cliques with three more vertices. The instance 7_5 is an important addition to the set of standard benchmarks for maximum clique problems, as it is of a similar size to the largest benchmarks, but no algorithm has been able to find a clique with 78 vertices that is known to exist. In summary, HTS2 finds the same size clique as SBTS for 46 instances, more slowly for 40 instances but faster for 4 instances. It finds a larger clique than SBTS for two instances, while SBTS never finds a larger clique than HTS2. **Supplementary Materials:** The following are available online at [[http://www.mdpi.com/1999-4893/13/10/253/s1](http://www.mdpi.com/1999-4893/13/10/253/s1)]([http://www.mdpi.com/1999-4893/13/10/253/s1](http://www.mdpi.com/1999-4893/13/10/253/s1)), Code for HTS2 is available in the Supplementary Material. **Author Contributions:** Development and presentation of original HTS algorithm, D.H.S., S.P. and R.M. ; conceptualization of graph coloring approach, D.H.S. and R.M. ; software development, D.H.S. ; permutation code benchmarks, D.H.S. and R.M., results, D.H.S. ; presentation, D.H.S., S.P. and R.M. All authors have read and agreed to the published version of the manuscript. **Funding:** This research received no external funding. **Conflicts of Interest:** The authors declare no conflict of interest. \begin{table}
\begin{tabular}{l c c c c} \hline \hline
**Instance** &
\begin{tabular}{c} **Optimal or Best Known** \\ **Number of Vertices** \\ \end{tabular} & **HTS (s)** & **HTS2 (s)** & **SBTS (s)** \\ \hline keller6 & 59 & 1057 & 1259 & 158.4 \\ C4000\_5 & 18 * & 390 & 312 & \textless{}1 \\ C2000\_9 & 80 & 658 (78 \(\circ\)) & 140,054 & 334,910 \\ 7\_4 & 349 & 1,353,356 & 258,579 & 21,336 \\ 7\_5 & 78 & 102,394 (73 \(\dagger\)) & 364,585 (75 \(\ddagger\)) & 215,270 (72 \(\ddagger\)) \\
8\_5 cyclic & 49 & 5163 & 6799 & 24,326.0 (46 \(\ddagger\)) \\
8\_5 ext. cyclic & 88 & 182 & 1 & 25.6 \\
10\_4 & 209 & 1257 & 3228 & 59.0 \\
10\_5 & 26 & 4 & 13 & 189.9 \\
11\_4 & 220 & 737 & 46 & 4.4 \\
11\_5 & 26 & 3 & 7 & \textless{}1 \\
12\_4 & 220 & 430 & 2 & 112.0 \\
12\_5 & 25 & & \textless{}1 & 2 \\ \hline \hline \end{tabular}

* \(\circ\) A clique with 80 vertices was found by HTS in [2] using a pre-processing method. \(\dagger\) [PERSON] and [PERSON] [3] report a much smaller time for successful runs, but only 2% of 100 runs were successful. \(\dagger\) 73 was found in 59,788 s but not improved in 906,471 s. \(\ddagger\) In addition, smaller cliques with 74 vertices were found 4 times in 364,585 s. \(\ddagger\) 72 was found in 215,270 s but not improved in 1,399,916.1 s. \(\ddagger\) 46 was found in 24,326.0 s but not improved in 61,097.2 s.

\end{table} 
Table 6: _Cont._

## References

* (1) [PERSON]; [PERSON]; [PERSON] Graph Colouring and Branch and Bound Approaches for Permutation Code Algorithms. In _New Advances in Information Systems and Technologies.