# The Use of an Exact Algorithm within a Tabu Search Maximum Clique Algorithm
## 1 Introduction  
Exact algorithms for the maximum clique problem are now remarkably efficient, but, for larger problems, heuristic algorithms are necessary. Tabu search is an effective metaheuristic for the maximum clique problem. This paper evaluates the option of including an exact algorithm within the tabu search, and considers the best exact algorithm to use. The candidate exact algorithms all use a graph coloring upper bound. This approach was used in the specific context of permutation code constructions in [1]. The final tabu search algorithm described, modified from a published algorithm [2], finds best known solutions to standard instances but is normally slower than a state-of-the-art tabu search algorithm [3] to find these solutions. However, it is more competitive for harder instances and actually finds significantly larger cliques for two open instances derived from the construction of permutation codes. Let \(G=(V,E)\) be an undirected graph with vertex set \(V\) and edge set \(E\). A clique \(C\) of \(G\) is a subset of the vertices of \(V\) with every pair of vertices of \(C\) adjacent (a complete subgraph). A maximum clique is a clique with the maximum number of vertices. Problems involving cliques arise in many applications surveyed in [4], including bioinformatics, examination planning, location problems, signal transmission analysis, and social network analysis. Applications of the maximum clique problem in radio frequency assignment are described in [5]. The problem also arises in the construction of various types of error-correcting code with the maximum number of codewords [6, 7]. Note that the problem of finding a maximum clique in the graph \(G\) is equivalent to the problem of finding a maximum independent set in the complement graph \(\overline{G}\). The decision form of the clique problem (does there exist a clique of size \(k\)) was proved to be one of the original 21 NP-complete problems in a classic paper [8]. It follows that the maximum clique problem is NP-hard. When exact methods are impractical, heuristic methods are used. Algorithms for the maximum clique problem, both exact and heuristic, are surveyed in [4]. The algorithm Swap-Based Tabu Search (SBTS) presented in [3] is the only heuristic algorithm compared in [4] that is able to find the optimal or best known solution over a wide range of instances. A more recent algorithm HTS (Hybrid Tabu Search) [2] also finds the optimal or best known solution over these instances and adds some further instances based on the construction of permutation codes [7]. HTS makes use of both an exact and a pseudoexact inner solver. In the tabu search in HTS, a number of carefully selected vertices are removed from the current clique before an exact or pseudoexact algorithm is applied to the subgraph induced by the set of vertices of \(G\) adjacent to all vertices in the reduced clique. As well as tabu search and other local search methods, there are also mathematical programming approaches, together with other methods, such as genetic algorithms, ant colony optimization, chemical reaction optimization, and particle swarm optimization. Hybrid and parallel versions of these algorithms also exist. The reader is referred to the survey [4] for an extensive list of references. Some later references to the maximum clique and related problems can be found in [9; 10; 11; 12; 13]. When comparable, these later approaches do not always match SBTS or HTS. For this reason, the current paper concentrates on tabu search. Although there are many effective algorithms, there is always scope for improvement on large and hard instances beyond the standard benchmarks. There are four objectives of this paper. The first is to determine the best exact algorithm to replace the exact and pseudoexact algorithms used in HTS. This allows a comparison of the resulting tabu search algorithm, incorporating the best exact algorithm found, with a more standard tabu search approach.