×

Algorithm for relatively small planted clique with small edge probability. (Chinese. English summary) Zbl 1399.68313

Summary: Planted clique problem is a central problem in average-case complexity theory. The random graph with planted clique model is extended, and small edge probability conditions are invented to allow the edge probability to decrease. It is shown that under such conditions there exists a polynomial-time randomized algorithm to find a relatively small planted clique by using probability tools for analysis of randomized algorithms. The result improves analysis of the algorithm in the literature.

MSC:

68W20 Randomized algorithms
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C80 Random graphs (graph-theoretic aspects)
68W40 Analysis of algorithms
PDFBibTeX XMLCite
Full Text: DOI