Abstract
The famous Planted Clique Problem was introduced 30 years ago by Jerrum along with a Monte Carlo (MC) algorithm to solve it. Jerrum demonstrated that its MC algorithm cannot find a planted clique of size K<=sqrt(N) , where N is the size of the graph, but he did not prove its success for K>=sqrt(N). I will show evidence that the Jerrum algorithm is not able to find the planted clique for a great range of K above K=sqrt(N). I will also show how the introduction of a mismatched parameter will enhance the performances of the MC method.