On Finding Randomly Planted Cliques in Arbitrary Graphs
Francesco Agrimonti, Marco Bressan, Tommaso D’Orsi · 2025
Read On Finding Randomly Planted Cliques in Arbitrary Graphs by Francesco Agrimonti, Marco Bressan, Tommaso D’Orsi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06725.txt.
Introduction
Francesco Agrimonti, Marco Bressan, and Tommaso d'Orsi study how to find a hidden complete graph planted in an arbitrary graph, in work from twenty twenty-five. A clique is a set of points all linked to each other. In the model, a large clique is placed at random inside a host graph with a cap on links per point.
The authors give a simple fixed rule method that runs in near linear time. It recovers a clique of a size set by the plant share and the link cap. The proof shows point degrees in the final graph track the hidden clique. The method also extends to hidden paired sets. Results split this planted case from the harder worst case.
Catalog record
| CREATOR | Francesco Agrimonti, Marco Bressan, Tommaso D’Orsi |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-06725
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On Finding Randomly Planted Cliques in Arbitrary Graphs Francesco Agrimonti, Marco Bressan, Tommaso D’Orsi Abstract We study a planted clique model introduced by Feige [ Rou19 ] where a complete graph of size c ⋅ n c\cdot n is planted uniformly at random in an arbitrary n n -vertex graph. We give a simple deterministic algorithm that, in almost linear time, recovers a clique of size ( c / 3 ) O ( 1 / c ) ⋅ n (c/3)^{O(1/c)}\cdot n as long as the original graph has maximum degree at most ( 1 − p ) n (1-p)n for some fixed p > 0 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 , 1 / 2 ) + K n G(n,\nicefrac{{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 ) \Omega(n) for every fixed c > 0 c>0 , even if the input graph has maximum degree ( 1 − p ) n (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. 1 Introduction Finding large cliques in a graph is a notoriously hard problem. Its decision version was among the first problems shown to be \mathsf{NP} -complete [ Kar72 ] . In fact, it turns out that for any \varepsilon>0 it is \mathsf{NP} -hard to find a clique of size n^{\varepsilon} even in graphs containing cliques of size n^{1-\varepsilon} [ Hås99 , Zuc06 , Kho01 ] . A large body of work [ CLRS09 , Hal93 , AK98 , KMS98 , Fei04 , BH06 , Kar09 ] focused on designing polynomial time algorithms to find large cliques given an n -vertex graph containing a clique of size cn\,. When c<1/\log n , the best algorithm known only returns a clique of size \tilde{O}(\log(n)^{3}) [ Fei04 ] . For larger values of c it is possible to find a clique of size O(cn)^{O(c)} , which is of order n^{\Omega(1)} when the largest clique in the graph contains a constant fraction of the vertices [ BH06 , AK98 ] . The current algorithmic landscape further suggests a phase-transition phenomenon around c=\tfrac{1}{2} . For sufficiently small \varepsilon>0 and c=\tfrac{1}{2}-\varepsilon there exists an algorithm finding a clique of size n^{1-O(\varepsilon)} [ KMS98 ] . Instead, when c=\tfrac{1}{2}+\varepsilon , one can efficiently find a complete graph of size 2\varepsilon n via a reduction to the classical 2-approximation algorithm for vertex cover. Finally, finding a clique of size \Omega(\varepsilon n) for c=\tfrac{1}{2}-\varepsilon was shown to be UGC-hard in [ KR08 , BK09 ] . Regime Output clique References c\geqslant\tfrac{1}{2}+\varepsilon 2\varepsilon n [ CLRS09 ] c\geqslant\Omega(1) (cn)^{\Omega(c)} [ AK98 ] c\geqslant 1/\log n \Omega\mathopen{}\mathclose{{\left(\frac{n^{c}}{c}}}\right) [ BH06 , Hal93 ] any c>0 \Omega\mathopen{}\mathclose{{\left(\frac{\log^{3}(cn)}{\log^{2}\log(cn)}}}\right) [ Fei04 ] Table 1: Performance of state-of-the-art efficient algorithms for clique when a clique of size cn exists in the graph (note that c can depend on n ). Given the grim worst-case picture, a substantial body of work has focused on designing algorithms that perform well under structural or distributional assumptions on the input graph. One research direction has investigated clique and related problems on graphs satisfying expansion or colorability properties [ AG11 , DF16 , KLT18 , BHK24 ] . Another line of work has explored planted average case models [ Kar72 , Jer92 , Kuč95 , AKS98 , FK00 , FK01 , CO03 , FO08 ] . In the planted clique model, the input graph is generated by sampling a graph from the Erdős-Rényi distribution \textnormal{ER}(n,\tfrac{1}{2}) and then embedding a clique of size cn by fully connecting a randomly chosen subset of vertices. Here, basic semidefinite programming relaxations [ FK00 , FK03 ] , as well a simple rounding of the second smallest eigenvector of the Laplacian [ AKS98 ] , are known to efficiently recover the planted clique whenever c\geqslant 1/\sqrt{n}\,. Lower bounds against restricted computational models further provide evidence that these algorithmic guarantees may be tight [ FGR+17 , BHK+19 ] . In an effort to bridge the worst-case settings and the average-case settings, Feige and Kilian [ FK01 ] introduced a semi-random model in which the above planted clique instance is further perturbed by: (i) arbitrarily removing edges between the planted clique K and the remainder of the graph G\setminus K , and (ii) arbitrarily modifying the subgraph induced by G\setminus K . The randomness of this model lies in the cut (K,G\setminus K) which separates the clique from the rest of the graph. A flurry of works [ CSV17 , MMT20 , BKS23 ] led to an algorithm that, leveraging the randomness of this cut, can recover a planted clique of size n^{\frac{1}{2}+\varepsilon} in time n^{O(1/\varepsilon)}\,. This picture suggests that, from a computational perspective, this semi-random model may be closer to the planted average case model than to worst-case graphs. (Information theoretically the semi-random model differs drastically from the planted clique model [ Ste17 ] .) To better understand the role of randomness in the clique problem, Feige [ Rou19 ] proposed another model in which a clique is randomly planted in an arbitrary graph, and asked what approximation guarantees are efficiently achievable in this setting. In comparison to the aforementioned semi-random case, here the randomness only affects the location of the clique but not the topology of the rest of the graph. Investigating this model is the main focus of this paper. We provide a first positive answer to Feige’s question, showing that a surprisingly simple deterministic algorithm achieves significantly stronger guarantees than those known for the worst-case settings, for a wide range of parameters. Our results suggest that this model may sit in between the average case and the worst case regimes. 1.1 Results To present our contributions we first formally state our random planting model. In fact, as our results extend beyond clique , the model we state is a generalization of the one in [ Rou19 ] . Definition 1.1 (Random planting in arbitrary graphs) . Let G and H be graphs with |V(H)|\leqslant|V(G)| . \mathcal{G}(G,H) describes the following distribution over graphs: 1. Sample a random uniform injective mapping \phi:V(H)\to V(G) . 2. Return \hat{G} with V(\hat{G})=V(G) and E(\hat{G})=E(G)\cup\mathopen{}\mathclose{{\left\{\{\phi(u),\phi(u^{\prime})\}\,:\,\{u,u^{\prime}\}\in E(H)}}\right\}\,. When H is the cn -sized complete graph K_{cn} , Definition 1.1 corresponds to the planted clique model of [ Rou19 ] . In this specific setting we obtain the following result. Theorem 1.2 (Simplified version) . There exists a deterministic algorithm \mathcal{A} with the following guarantees. For every c\in(0,1) and every n -vertex graph G , if \hat{G}\sim\mathcal{G}\mathopen{}\mathclose{{\left(G,K_{cn}}}\right) then \mathcal{A}(\hat{G}) with probability at least 1-\tfrac{1}{n^{2}} returns a clique of size at least: \displaystyle\frac{n}{5}\cdot\mathopen{}\mathclose{{\left(\frac{c}{3}}}\right)^{\tfrac{4}{c}\log\tfrac{2}{p}} where p=1-\frac{\Delta}{n} and \Delta is the maximum degree of G . Moreover \mathcal{A} runs in time \tilde{O}\big(\lVert\hat{G}\rVert\big) . To appreciate the guarantees of Theorem 1.2 consider the setting p=\Omega(1) , so that \Delta=(1-p)n is bounded away from