Neighborhood structures and local search for the maximum clique problem

The Maximum Clique is an NP-hard problem aiming at finding the largest complete sub-graph in a given graph. In this approach we intend to find a lower bound for the maximization problem. Firstly, the neighborhood structures are defined according to the feasibility and the type of move. Secondly, based on the created structures the constructive and the improvement heuristics are explained. Initially we describe two constructive heuristics (primal and dual) proposed by Johnson and a heuristic that uses Tabu Search, developed by Soriano and Gendreau, that we call Primal Tabu. Afterwards a new heuristic is presented, named Dual Tabu due to its working with non-feasible solutions. This new heuristic, still based on the defined neighborhood structures, incorporates an oscillation strategy that drags the solution from the feasible solution space to the non-feasible space and vice-versa. The computational results with DIMACS clique benchmark instances presented are obtained with a hybrid heuristic Primal–Dual Tabu, that takes advantage of the complementary strategies.