Scholarlink

In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [15] which has been studied in many other works [8, 11, 16, 25, 34, 37] 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 work of Khanna and Louis [24]. As a by-product of our main result, we give an alternate SDP-based rounding algorithm (with similar guarantees) for solving the Planted Clique problem in a random graph.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Exact Recovery of Planted Cliques in Semi-random Graphs

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Yash Khanna

摘要

In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [15] which has been studied in many other works [8, 11, 16, 25, 34, 37] 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 work of Khanna and Louis [24]. As a by-product of our main result, we give an alternate SDP-based rounding algorithm (with similar guarantees) for solving the Planted Clique problem in a random graph.