论文标题
半随机图中种植集团的精确恢复
Exact recovery of Planted Cliques in Semi-random graphs
论文作者
论文摘要
在本文中，我们在半随机模型中研究了种植的集团问题。我们的模型灵感来自Feige-Kilian模型[FK01]，该模型在许多其他作品[FK00，Ste17，MMT20]中进行了研究。我们的算法和分析与Khanna和Louis [KL20]最近的工作中最密集的$ k $ -subgraph问题所研究的算法相似。但是，由于我们的算法完全恢复了种植的集团W.H.P. （对于“大型”输入参数），我们需要一些新想法。 作为我们主要结果的副产品，我们给出了一种基于SDP的替代圆形算法（具有匹配保证），用于在随机图中解决植物集团问题。此外，当种植的子图是一个集团而不是任意$ d $ regular Graph时，我们能够解决[KL20]中最密集的$ k $ -subgraph问题引入的模型的特殊情况。
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 [FK00, Ste17, MMT20] for a variety of graph problems. 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. (for a "large" range of input parameters), 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 models introduced for the Densest $k$-subgraph problem in [KL20], when the planted subgraph is a clique instead of an arbitrary $d$-regular graph.
