In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [FK01] which has been studied in many other works [Ste17, MMT20]. Our algorithm and analysis is on similar lines to the one studied for the Densest $k$-subgraph problem in the recent work of Khanna and Louis [KL20]. However since our algorithm fully recovers the planted clique w.h.p., we require some new ideas. As a by-product of our main result, we give an alternate SDP based rounding algorithm (with matching guarantees) for solving the Planted Clique problem in a random graph. Also, we are able to solve special cases of the D$k$SReg$(n, k, d, \delta, \gamma)$ and D$k$SReg$(n, k, d, \delta, d', \lambda)$ models introduced in [KL20], when the planted subgraph $\mathcal{G}[\mathcal{S}]$ is a clique instead of an arbitrary $d$-regular graph.
翻译：在本文中,我们研究半随机模型中的原克隆问题。我们的模型来自Feige-Kilian模型[FK01],该模型已在许多其他作品[Ste17,MMT20]中研究过。我们的算法和分析与Khanna和Louis[KL20]最近工作中为Densest $k$-Subgragy问题所研究的类似。然而,由于我们的算法完全恢复了种植的cloique w.h.p.,我们需要一些新想法。作为我们主要结果的副产品,我们提供了一种基于SDP的替代四舍五入算法(配对保证),以随机图表解决原克隆问题。此外,我们还能够解决Dk$(n, k, d, delta,\ gamma) 和 Dk$(n, k, d, d, delta, d', d',\lambda) 美元模式的特殊案例。当植入 [KL20] 的Subraphal $-macalqal = a a rotical= a macrotical *{G}[macal] a a cal_Q{G}}}
相关内容
微信扫码咨询专知VIP会员