Finding Hidden Cliques in Linear Time with High Probability
Finding Hidden Cliques in Linear Time with High Probability
复制标题
DOI：
10.1017/s096354831300045x
复制
发表时间：
2014-01-01
影响因子：
0.9
通讯作者：
Peres, Yuval
中科院分区：
文献类型：
--
作者：
Dekel, Yael;Gurel-Gurevich, Ori;Peres, Yuval
给定一个n阶图G，其中k个顶点的随机子集被构造成一个团，其余的边以1/2的概率被独立地选择。这个随机图模型记为G（n，1/2，k）。隐藏团问题是设计一个算法，在多项式时间内以高概率找到k-团。Alon、Krivelevich和Sudakov [3]的算法使用谱技术来找到隐藏团，当k = c root n时，对于足够大的常数c > 0，具有高概率。最近，Feige和罗恩[12]提出了一种解决相同问题的算法。它的优点是更简单，更直观，并改善了O（n（2））的运行时间。然而，[12]中的分析给出的成功概率仅为2/3。在本文中，我们提出了一个新的算法来寻找隐藏的集团，都运行在时间O（n（2））（即，线性的输入的大小），并有一个失败的概率，趋于0的n趋于无穷大。我们开发这个算法在更一般的设置，集团是由一个密集的随机图取代。
We are given a graph G with n vertices, where a random subset of k vertices has been made into a clique, and the remaining edges are chosen independently with probability 1/2. This random graph model is denoted G(n, 1/2, k). The hidden clique problem is to design an algorithm that finds the k-clique in polynomial time with high probability. An algorithm due to Alon, Krivelevich and Sudakov [3] uses spectral techniques to find the hidden clique with high probability when k = c root n for a sufficiently large constant c > 0. Recently, an algorithm that solves the same problem was proposed by Feige and Ron [12]. It has the advantages of being simpler and more intuitive, and of an improved running time of O(n(2)). However, the analysis in [12] gives a success probability of only 2/3. In this paper we present a new algorithm for finding hidden cliques that both runs in time O(n(2)) (that is, linear in the size of the input) and has a failure probability that tends to 0 as n tends to infinity. We develop this algorithm in the more general setting where the clique is replaced by a dense random graph.