On Finding Randomly Planted Cliques in Arbitrary Graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909607191904256 |
|---|---|
| author | Agrimonti, Francesco Bressan, Marco d'Orsi, Tommaso |
| author_facet | Agrimonti, Francesco Bressan, Marco d'Orsi, Tommaso |
| contents | We study a planted clique model introduced by Feige where a complete graph of size $c\cdot n$ is planted uniformly at random in an arbitrary $n$-vertex graph. We give a simple deterministic algorithm that, in almost linear time, recovers a clique of size $(c/3)^{O(1/c)} \cdot n$ as long as the original graph has maximum degree at most $(1-p)n$ for some fixed $p>0$. The proof hinges on showing that the degrees of the final graph are correlated with the planted clique, in a way similar to (but more intricate than) the classical $G(n,\frac{1}{2})+K_{\sqrt{n}}$ planted clique model. Our algorithm suggests a separation from the worst-case model, where, assuming the Unique Games Conjecture, no polynomial algorithm can find cliques of size $Ω(n)$ for every fixed $c>0$, even if the input graph has maximum degree $(1-p)n$. Our techniques extend beyond the planted clique model. For example, when the planted graph is a balanced biclique, we recover a balanced biclique of size larger than the best guarantees known for the worst case. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_06725 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Finding Randomly Planted Cliques in Arbitrary Graphs Agrimonti, Francesco Bressan, Marco d'Orsi, Tommaso Computational Complexity Discrete Mathematics 68W25 F.2.2 We study a planted clique model introduced by Feige where a complete graph of size $c\cdot n$ is planted uniformly at random in an arbitrary $n$-vertex graph. We give a simple deterministic algorithm that, in almost linear time, recovers a clique of size $(c/3)^{O(1/c)} \cdot n$ as long as the original graph has maximum degree at most $(1-p)n$ for some fixed $p>0$. The proof hinges on showing that the degrees of the final graph are correlated with the planted clique, in a way similar to (but more intricate than) the classical $G(n,\frac{1}{2})+K_{\sqrt{n}}$ planted clique model. Our algorithm suggests a separation from the worst-case model, where, assuming the Unique Games Conjecture, no polynomial algorithm can find cliques of size $Ω(n)$ for every fixed $c>0$, even if the input graph has maximum degree $(1-p)n$. Our techniques extend beyond the planted clique model. For example, when the planted graph is a balanced biclique, we recover a balanced biclique of size larger than the best guarantees known for the worst case. |
| title | On Finding Randomly Planted Cliques in Arbitrary Graphs |
| topic | Computational Complexity Discrete Mathematics 68W25 F.2.2 |
| url | https://arxiv.org/abs/2505.06725 |