Taking a small graph, on which the randomized New-Best-In maximum clique heuristic fails to find the maximum clique, we construct on its basis a class of graphs exemplifying the inefficiency of SM greedy heuristics considered by Brockington and Culberson. We show that a 7(k+1)-vertex graph from this class is enough to provide a counterexample for the SM^k heuristic. On the other hand, two recent continuous heuristics — Max-AO and QUALEX-MS — successfully find exact solutions on the considered graphs.
Citation
Stas Busygin's NP-Completeness Page (http://www.busygin.dp.ua/npc.html), 2002.