The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908812167872512 |
|---|---|
| author | Hou, Jiaxin Soh, Yong Sheng Varvitsiotis, Antonios |
| author_facet | Hou, Jiaxin Soh, Yong Sheng Varvitsiotis, Antonios |
| contents | The problems of computing graph colorings and clique covers are central challenges in combinatorial optimization. Both of these are known to be NP-hard, and thus computationally intractable in the worst-case instance. A prominent approach for computing approximate solutions to these problems is the celebrated Lovász theta function $\vartheta(G)$, which is specified as the solution of a semidefinite program (SDP), and hence tractable to compute. In this work, we move beyond the worst-case analysis and set out to understand whether the Lovász theta function recovers clique covers for random instances that have a latent clique cover structure, possibly obscured by noise. We answer this question in the affirmative and show that for graphs generated from the planted clique model we introduce in this work, the SDP formulation of $\vartheta(G)$ has a unique solution that reveals the underlying clique-cover structure with high-probability. The main technical step is an intermediate result where we prove a deterministic condition of recovery based on an appropriate notion of sparsity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_00257 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings Hou, Jiaxin Soh, Yong Sheng Varvitsiotis, Antonios Optimization and Control Data Structures and Algorithms Information Theory Combinatorics The problems of computing graph colorings and clique covers are central challenges in combinatorial optimization. Both of these are known to be NP-hard, and thus computationally intractable in the worst-case instance. A prominent approach for computing approximate solutions to these problems is the celebrated Lovász theta function $\vartheta(G)$, which is specified as the solution of a semidefinite program (SDP), and hence tractable to compute. In this work, we move beyond the worst-case analysis and set out to understand whether the Lovász theta function recovers clique covers for random instances that have a latent clique cover structure, possibly obscured by noise. We answer this question in the affirmative and show that for graphs generated from the planted clique model we introduce in this work, the SDP formulation of $\vartheta(G)$ has a unique solution that reveals the underlying clique-cover structure with high-probability. The main technical step is an intermediate result where we prove a deterministic condition of recovery based on an appropriate notion of sparsity. |
| title | The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings |
| topic | Optimization and Control Data Structures and Algorithms Information Theory Combinatorics |
| url | https://arxiv.org/abs/2310.00257 |