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.
HUANG Xuangui
. Algorithm for Relatively Small Planted Clique with
Small Edge Probability[J]. Journal of Shanghai Jiaotong University, 2017
, 51(10)
: 1202
-1206
.
DOI: 10.16183/j.cnki.jsjtu.2017.10.008
［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.
