In the planted clique problem, the input is generated from a random graph (edge probability 1/2) by adding edges that complete a random set H of k vertices into a clique. One needs to find H.
In the talk I will present some experimental algorithmic results obtained together with Dorit Ron. Providing rigorous analysis for these algorithms remains a challenge.
In the planted dense k-subgraph problem, the input graph G is generated by first picking a random graph of average degree D, and then, for a random set H of k vertices, adding to it random edges so as to make it a random graph of average degree d. The goal is to recover H. I will describe the known algorithmic result for the planted k-subgraph problem, and describe open questions in the planted model whose resolution is essential if one is to see progress in improving the known approximation ratios for dense k-subgraph (for general graphs, not assuming the planted model).
This part of the talk is based on work with Eden Chlamtac.
Quite similar results were obtained independently by Bhaskara, Charikar and Vijayaraghavan.
Copyright. All Rights Reserved.