A Simple Clique Camouflaging Against Greedy Maximum Clique Heuristics

Stanislav Busygin (busygina-teleport.com)

Abstract: 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.

Keywords: maximum clique, greedy heuristics, forbidden subgraphs, continuous approach, algorithms, NP-hard

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Stas Busygin's NP-Completeness Page (http://www.busygin.dp.ua/npc.html), 2002.

Download: [Postscript][Compressed Postscript]

Entry Submitted: 12/19/2002
Entry Accepted: 12/22/2002
Entry Last Modified: 12/19/2002

Modify/Update this entry