2026-07-25T15:15:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24377 2025-12-12T15:01:13Z ddc:004 open_access

On Finding Randomly Planted Cliques in Arbitrary Graphs Agrimonti, Francesco Bressan, Marco d'Orsi, Tommaso Computational Complexity Planted Clique Semi-random Unique Games Conjecture Approximation Algorithms We study a planted clique model introduced by Feige [Uriel Feige, 2021] where a complete graph of size c⋅ 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) ⋅ 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,1/2)+K_√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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Francesco Agrimonti and Marco Bressan and Tommaso d'Orsi 2025 Is Part Of LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2025.11 urn:nbn:de:0030-drops-243774 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.11 eng https://creativecommons.org/licenses/by/4.0/legalcode