针对植入团问题是平均情况复杂性理论的一个中心问题，将带植入团的随机图模型进行推广，提出小边概率条件，使得边概率可以随着顶点数目的增大而变小.使用随机算法分析中的概率工具，改进文献中算法的分析，证明在小边概率条件下，存在以很大概率找到推广模型中较小的植入团的多项式时间随机算法.
Planted clique problem is a central problem in averagecase 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 polynomialtime 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.
［1］HASTAD J. Clique is hard to approximate within n1－ε［C］∥Proceedings of The 37th Annual Symposium on Foundations of Computer Science. Washington, DC: IEEE Computer Society, 1996: 627636.
［2］JANSON S, LUCZAK T, RUCINSKI A. Random graphs［M］. New York: John Wiley & Sons, 2000.
［3］ARORA S, BARAK B. Computational complexity: A modern approach［M］. New York: Cambridge University Press, 2009: 361372.
［4］KARP R M. The probabilistic analysis of some combinatorial search algorithms［C］∥Algorithms and Complexity: New Directions and Recent Results. New York: Academic Press, 1976: 119.
［5］JERRUM M. Large cliques elude the Metropolis process［J］. Random Structures and Algorithms, 1992, 3(4): 347359.
［6］KUERA L. Expected complexity of graph partitioning problems［J］. Discrete Applied Mathematics, 1995, 57(2): 193212.
［7］ALON N, KRIVELEVICH M, SUDAKOV B. Finding a large hidden clique in a random graph［J］. Random Structures and Algorithms, 1998, 13(3/4): 457466.
［8］FEIGE U, RON D. Finding hidden cliques in linear time［C］∥Proceedings of The 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms. Nancy, France: Discrete Mathematics and Theoretical Computer Science (DMTCS), 2010: 189204.
［9］DEKEL Y, GURELGUREVICH O, PERES Y. Finding hidden cliques in linear time with high probability［C］∥Proceedings of the Meeting on Analytic Algorithmics and Combinatorics. San Francisco: Society for Industrial and Applied Mathematics, 2011: 6775.
［10］AMES B P W, VAVASIS S A. Nuclear norm minimization for the planted clique and biclique problems［J］. Mathematical Programming, 2011, 129(1): 6989.
［11］DESHPANDE Y, MONTANARI A. Finding hidden cliques of size N/e in nearly linear time［J］. Foundations of Computational Mathematics, 2015, 15(4): 10691128.
［12］FELDMAN V, GRIGORESCU E, REYZIN L, et al. Statistical algorithms and a lower bound for detecting planted cliques［C］∥Proceedings of The 45th Annual ACM Symposium on Theory of Computing. Palo Alto, USA: Association for Computing Machinery, 2013: 655664.
［13］MEKA R, POTECHIN A, WIGDERSON A. Sumofsquares lower bounds for planted clique［C］∥Proceedings of the 47th Annual ACM Symposium on Theory of Computing. Portland, USA: Association for Computing Machinery, 2015: 8796.
［14］DESHPANDE Y, MONTANARI A. Improved sumofsquares lower bounds for hidden clique and hidden submatrix problems［C］∥Proceedings of The 28th Conference on Learning Theory. Paris, France: JMLR, Inc, 2015: 523562.
［15］HAZAN E, KRAUTHGAMER R. How hard is it to approximate the best Nash equilibrium?［J］. SIAM Journal on Computing, 2011, 40(1): 7991.
［16］SANTHANAM R. The complexity of explicit constructions［J］. Theory of Computing Systems, 2012, 51(3): 297312.
［17］HAJEK B, WU Y, XU J. Computational lower bounds for community detection on random graphs［C］∥Proceedings of The 28th Conference on Learning Theory. Paris, France: JMLR, Inc, 2015: 899928.
