Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2011.08447 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912752530882560 |
|---|---|
| author | Khanna, Yash |
| author_facet | Khanna, Yash |
| contents | In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [16] which has been studied in many other works [8,11,17,26,35,38] 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 [25].
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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2011_08447 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Exact recovery of planted cliques in semi-random graphs Khanna, Yash Data Structures and Algorithms In this paper, we study the Planted Clique problem in a semi-random model. Our model is inspired from the Feige-Kilian model [16] which has been studied in many other works [8,11,17,26,35,38] 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 [25]. 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. |
| title | Exact recovery of planted cliques in semi-random graphs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2011.08447 |