Finding hidden cliques in linear time
Finding hidden cliques in linear time
复制标题
在线性时间内寻找隐藏的派系
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
U. Feige
中科院分区：
文献类型：
--
作者：
D. Ron;U. Feige
在隐藏团问题中，需要在一个$n$-顶点图中找到最大团，该图具有大小为$k$的团，但在其他方面是随机的。一个算法的阿隆，Krivelevich和Sudakov是基于谱技术是已知的，以解决这个问题（具有高概率的随机选择的输入图）时，$k geq c sqrt{n}$一个足够大的常数$c$。在这篇手稿中，我们提出了一个新的算法，寻找隐藏的集团。当k > c sqrt{n}$时，它也可以证明是有效的，因为c$足够大。然而，我们的算法的优点是更简单（不使用光谱技术），运行速度更快（线性时间），实验表明，领先的常数$c$小于光谱方法。我们还提出了线性时间算法，实验发现更小的隐藏集团，但它仍然开放，这些算法是否发现隐藏集团的大小为$o（sqrt{n}）$。
In the hidden clique problem, one needs to find the maximum clique in an $n$-vertex graph that has a clique of size $k$ but is otherwise random. An algorithm of Alon, Krivelevich and Sudakov that is based on spectral techniques is known to solve this problem (with high probability over the random choice of input graph) when $k geq c sqrt{n}$ for a sufficiently large constant $c$. In this manuscript we present a new algorithm for finding hidden cliques. It too provably works when $k > c sqrt{n}$ for a sufficiently large constant $c$. However, our algorithm has the advantage of being much simpler (no use of spectral techniques), running faster (linear time), and experiments show that the leading constant $c$ is smaller than in the spectral approach. We also present linear time algorithms that experimentally find even smaller hidden cliques, though it remains open whether any of these algorithms finds hidden cliques of size $o(sqrt{n})$.