Algorithm for Relatively Small Planted Clique with
 Small Edge Probability

doi:10.16183/j.cnki.jsjtu.2017.10.008

Abstract

Abstract: 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.

Key words: random graph; planted clique; small edge probability; randomized algorithm; average case complexity

CLC Number:

TP 301.6

HUANG Xuangui. Algorithm for Relatively Small Planted Clique with
Small Edge Probability[J]. Journal of Shanghai Jiao Tong University, 2017, 51(10): 1202-1206.

References

［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: 627636.
［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: 361372.
［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: 119.
［5］JERRUM M. Large cliques elude the Metropolis process［J］. Random Structures and Algorithms, 1992, 3(4): 347359.
［6］KUERA L. Expected complexity of graph partitioning problems［J］. Discrete Applied Mathematics, 1995, 57(2): 193212.
［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): 457466.
［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: 189204.
［9］DEKEL Y, GURELGUREVICH 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: 6775.
［10］AMES B P W, VAVASIS S A. Nuclear norm minimization for the planted clique and biclique problems［J］. Mathematical Programming, 2011, 129(1): 6989.
［11］DESHPANDE Y, MONTANARI A. Finding hidden cliques of size N/e in nearly linear time［J］. Foundations of Computational Mathematics, 2015, 15(4): 10691128.
［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: 655664.
［13］MEKA R, POTECHIN A, WIGDERSON A. Sumofsquares lower bounds for planted clique［C］∥Proceedings of the 47th Annual ACM Symposium on Theory of Computing. Portland, USA: Association for Computing Machinery, 2015: 8796.
［14］DESHPANDE Y, MONTANARI A. Improved sumofsquares lower bounds for hidden clique and hidden submatrix problems［C］∥Proceedings of The 28th Conference on Learning Theory. Paris, France: JMLR, Inc, 2015: 523562.
［15］HAZAN E, KRAUTHGAMER R. How hard is it to approximate the best Nash equilibrium?［J］. SIAM Journal on Computing, 2011, 40(1): 7991.
［16］SANTHANAM R. The complexity of explicit constructions［J］. Theory of Computing Systems, 2012, 51(3): 297312.
［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: 899928.

[1]	ZHAO Ziren1, DU Shichang1, HUANG Delin1, REN Fei2, LIANG Xinguang2. Modelling and Bottleneck Analysis of Product Quality in Transient Phase#br# of MultiStage Manufacturing Systems Based on Markovian Chains [J]. Journal of Shanghai Jiao Tong University, 2017, 51(10): 1166-1173.
[2]	ZHOU Penghui, MA Hongzhan, CHEN Dongping, CHEN Mengyue, CHU Xuening. Identification of Product Redesign Modules Based on#br# Fuzzy Random Failure Mode and Effects Analysis [J]. Journal of Shanghai Jiao Tong University, 2017, 51(10): 1189-1195.
[3]	LI Changxi1, 2, ZHOU Yan1, LIN Han3, LI Lingzhi1, GUO Ge1. TemporalSpatial Sequential Fusion Recognition Method of#br# Ballistic Missile Target Based on MIMOFNN Model [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1138-.
[4]	FENG Mingyue, HE Minghao, HAN Jun, YU Chunlai. High Resolution Direction of Arrival Estimation Based on#br# Covariance Fitting Estimation of Signal Parameters by#br# Rotational Invariance Technique Algorithm [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1145-.
[5]	?YANG Ping1,SHENG Jie1,WANG Yucheng2,LI Zhuyong1,JIN Zhijian1,HONG Zhiyong1. Quench Propagation Characteristics Influenced by NonUniform Properties of YBa2Cu3O7δ High Temperature Superconducting Tape [J]. Journal of Shanghai Jiaotong University, 2017, 51(9): 1090-1096.
[6]	WANG Xing, ZHOU Yipeng, TIAN Yuanrong, CHEN You, ZHOU Dongqing, HE Jiyuan. Sparse Decomposition for Frequency Modulation Radar Signal Based on#br# Advanced Genetic Algorithm and SinChirplet Atom [J]. Journal of Shanghai Jiao Tong University, 2017, 51(9): 1124-1130.
[7]	ZHANG Liangjun1, 2, LI Xiaoci1, WU Jingyi1, CAI Aifeng1. ThermalStructure Coupling Analysis of #br# Microgravity Environment Simulation Suspension Structure for #br# Large Space Deployable Mechanisms [J]. Journal of Shanghai Jiao Tong University, 2017, 51(8): 954-961.
[8]	XIA Hailiang1, 2, LIU Yakun1, 2, LIU Quanzhen3, LIU Baoquan3, FU Zhengcai1, 2. Metal Ablation Affected by Electrode Shapes Under#br# Long Continuing Lightning Current [J]. Journal of Shanghai Jiao Tong University, 2017, 51(8): 903-908.
[9]	GU Jiayang, XIE Yulin, TAO Yanwu, HUANG Xianghong, WU Jie. Numerical Simulation and Experimental Study on VortexInduced#br# Motion of a New Type of Floating Drilling Production Storage Offloading [J]. Journal of Shanghai Jiao Tong University, 2017, 51(7): 878-885.
[10]	LIN Da, ZHU Yijia, WEI Xiaodong, WANG Zhiyu, ZHANG Wugao. Combustion and Particle Emission Characteristics Affected by#br# Fuel Supply Parameters for a Diesel Engine Fuelled with#br# Polyoxymethylene Dimethyl Ethers/Diesel [J]. Journal of Shanghai Jiao Tong University, 2017, 51(7): 787-795.
[11]	MENG Qingyang1, YAN Weiwu1, HU Yong1, CHENG Jianlin1, CHEN Shihe2, ZHANG Xi2. Model Identification Based on Subspace Model Identification of#br# Superheated Steam System in UltraSupercritical CoalFired Power Unit [J]. Journal of Shanghai Jiao Tong University, 2017, 51(6): 672-678.
[12]	JIANG Huajuna, CAI Yana, b, LI Chaohaoa, LI Fanga, b, HUA Xueminga, b. Recognition Method for Gas Pores on XRay Image of Lap Joints#br# Based on the Improved Sobel Algorithm [J]. Journal of Shanghai Jiao Tong University, 2017, 51(6): 665-671.
[13]	DONG Guanhua,YIN Qin,YIN Guofu,XIANG Zhaowei. Identification and Modeling of Coupling Dynamic Stiffness in Joints of Machine Tool [J]. Journal of Shanghai Jiaotong University, 2015, 49(09): 1263-1434.
[14]	XIE Qijiang,YU Haidong. Coupling Relationship Between Loads on Cutterhead of Tunnel Boring Machine and Contact Stiffness of Gripper Shoes and Rocks [J]. Journal of Shanghai Jiaotong University, 2015, 49(09): 1269-1275.
[15]	ZHONG Jianlin1,MA Dawei1,REN Jie1,LI Shijun2,WANG Xu3. Static Compression Analysis of Rubber Hollow Cylinder Based on Plane Strain Assumption [J]. Journal of Shanghai Jiaotong University, 2015, 49(09): 1276-1280.