Hard graphs for the randomized Boppana-Halldórsson algorithm for MAXCLIQUE
Marcus Peinado · 1994
. A randomized version of the Maxclique approximation algorithm by Boppana and Halld'orsson is analyzed. The Boppana Halld'orsson algorithm has the best performance guarantee currently known for the Maxclique problem. This paper presents a class of graphs on which the performance ratio of the randomized version of the algorithm is not better than\\Omega\\Gamma p n) with probability greater than 1 \\Gamma 1=n !(1) . Key words: approximation algorithms, Maxclique, randomization CR Classification: F.2.2, G.2.1, G.2.2, G.3 1. Introduction Unlike many other NP-hard problems, the Maxclique problem has resisted attempts to find efficient approximation algorithms. Indeed, the well known result of Arora et al. [1992] proves that no deterministic polynomial time algorithm can approximate the maximum clique in a graph to within a factor of n c for some (very small) c ? 0 unless P = NP . The performance of an approximation algorithm A for Maxclique on an input graph G is generally measured by ...