Loading...
Please wait, while we are loading the content...
Similar Documents
Finding hidden cliques of size √ n/e in nearly linear time (2013).
| Content Provider | CiteSeerX |
|---|---|
| Author | Deshpande, Yash Montanari, Andrea |
| Abstract | Consider an Erdös-Renyi random graph in which each edge is present independently with probability 1/2, except for a subset CN of the vertices that form a clique (a completely connected subgraph). We consider the problem of identifying the clique, given a realization of such a random graph. The best known algorithm provably finds the clique in linear time with high probability, provided CN ≥ 1.261 √ N [YDP11]. Spectral methods can be shown to fail on cliques smaller than √ N. In this paper we describe a nearly linear time algorithm that succeeds with high probability for CN ≥ (1 + ε) √ N/e for any ε> 0. This is the first algorithm that provably improves over spectral methods. We further generalize the hidden clique problem to other background graphs (the standard case corresponding to the complete graph on N vertices). For large girth regular graphs of degree ( ∆ + 1) we prove that ‘local ’ algorithms succeed if CN ≥ (1 + ε)N / √ e ∆ and fail if CN ≤ (1 − ε)N / √ e∆. |
| File Format | |
| Publisher Date | 2013-01-01 |
| Access Restriction | Open |
| Subject Keyword | Hidden Clique Nearly Linear Time Spectral Method High Probability Background Graph Known Algorithm Complete Graph Linear Time Algorithm Large Girth Regular Graph Random Graph Standard Case Linear Time Local Algorithm Hidden Clique Problem First Algorithm Erd S-renyi Random Graph Subset Cn |
| Content Type | Text |
| Resource Type | Article |
