# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 3 Minor Improvements in HTS2
```
1:\(\textbf{ts\_Optimize(C)}\);
2:\(\textit{Ts\_count}:=0\);
3:\(\textit{Tabulist}:=\varnothing\); \(\textit{Tscurrent}:=C\); \(\textit{Tscbest}:=C\);
4:while (\(\textit{Ts\_count}<10000\)) do
5:\(\textit{Ts\_count}:=\textit{Ts\_count}+1\); \(\textit{Aspiration}:=\textit{False}\);
6:for all \(v\in\textit{Tscurrent}\)do
7:\(\textit{Best}:=\varnothing\); \(\textit{External\_lower\_bound}:=|\textit{Tscbest}|-|\textit{Tscurrent}|+1\);
8:\(\textit{Exact(\varnothing,N(\textit{Tscurrent}\setminus\{v\}))}\);
9:\(\textit{Tsctemp1}:=\textit{Best}\cup(\textit{Tscurrent}\setminus\{v\})\);
10: Update a list \(L_{1}\) of all \(v\in\textit{Tscurrent}\) with \(|\textit{Ttemp1}|\) maximal (and for this value of \(|\textit{Tstemp1}|\) the value \(|\textit{N(\textit{Tscurrent}\setminus\{v\})}|\) is maximal);
11:if\(|\textit{Tstemp1}|>|\textit{Tscbest}|\)then
12:\(\textit{Aspiration}:=\textit{True}\);
13:else
14:\(\textit{Notnabu}:=\{u\in N(\textit{Tscurrent}\setminus\{v\})|w\
otin \textit{Tabulist}\}\);
15:\(\textit{Best}:=\varnothing\); \(\textit{External\_lower\_bound}:=0\);
16:\(\textit{Exact(\varnothing,N(\textit{Tscurrent}\setminus\{v\}))}\);
17:\(\textit{Tstemp2}:=\textit{Best}\cup(\textit{Tscurrent}\setminus\{v\})\);
18: Update a list \(L_{2}\) of all \(v\in\textit{Tscurrent}\) with \(|\textit{Tstemp2}|\) maximal (and for this value of \(|\textit{Tstemp2}|\) the value \(|\textit{Nontabu}|\) is maximal);
19:endif
20:endfor
21:ifAspiration = true then
22: select \(v^{\prime}\in L_{1}\) randomly;
23:\(\textit{Best}:=\varnothing\); \(\textit{External\_lower\_bound}:=|\textit{Tscbest}|-|\textit{Tscurrent}|+1\);
24:\(\textit{Exact(\varnothing,N(\textit{Tscurrent}\setminus\{v^{\prime}\}))}\);
25:\(\textit{Tscurrent}:=\textit{Best}\cup(\textit{Tscurrent}\setminus\{v^{ \prime}\})\); \(\textit{Tscbest}:=\textit{Tscurrent}\);
26:\(\textit{Ts\_count}:=0\);
27:else
28: Select \(v^{\prime\prime}\in L_{2}\) randomly;
29:\(\textit{Tscurrent}:=\textit{Tscurrent}\setminus\{v^{\prime\prime}\}\);
30: Add \(v^{\prime\prime}\) to \(\textit{Tabulist}\) (removing oldest entry if list length exceeds _Tstenure_);
31:if\(|\textit{Tscurrent}|\leq\textit{Tscset}min+1\)then
32:\(\textit{Notnabu}:=\{w\in N(\textit{Tscurrent})|w\
otin\textit{Tabulist}\}\);
33:if\(|\textit{Notnabu}|<\lambda_{2}\)then
34:\(\textit{Best}:=\varnothing\); \(\textit{External\_lower\_bound}:=0\);
35:\(\textit{Exact(\varnothing,Nontabu)}\);
36:\(\textit{Tscurrent}:=\textit{Best}\cup\textit{Tscurrent}\);
37:else
38: Select \(v^{\prime\prime\prime}\in\textit{Notnabu}\) randomly;
39:\(\textit{Tscurrent}:=\{v^{\prime\prime\prime}\}\cup\textit{Tscurrent}\);
40:endif
41:endif
42:endif
43:endif
44:if\(|\textit{Tscbest}|>|C|\)then
45:\(C:=\textit{Tscbest}\);
46:endif
47:return(C);
```

**Algorithm 5**Tabu search. ## 4 Simplification of Parameters

There are several parameters used in HTS. These are not difficult to determine by a short exploratory run, but it is more convenient if most of them are determined by the algorithm itself. The parameters in question are \(\theta_{1}\), \(\theta_{2}\), \(\theta_{3}\), \(\theta_{\text{ts}}\), \(\lambda_{1}\), \(\lambda_{2}\), _Tsttime_, _Tstenure_, and _Tssetmin_. Pseudoexact search in HTS also has a number of coefficients, but these are no longer relevant as pseudoexact search is not used in HTS2. The use of _Tsttime_ was replaced by a condition \"10,000 iterations without improvement\" in the previous section. The four \(\theta\) parameters in HTS are replaced in HTS2 by a single parameter \(\theta\) (see Algorithm 2) determined as follows. The main heuristic is run 100 times. If the largest clique \(C_{\max}\) found is not unique, then \(\theta=|C_{\max}|\). If this value is unique, then \(\theta\) is the number of vertices in the second largest clique. This ensures that the other optimizations are only applied to the most promising cliques generated, but avoids single outliers that might only be generated very rarely in later iterations. The two parameters \(\lambda_{1}\) and \(\lambda_{2}\) are used in the main heuristic (see Algorithm 3).