标题： 洛瓦兹θ函数用于恢复种植的团覆盖和图着色 显示英文标题

标题： The Lovász Theta Function for Recovering Planted Clique Covers and Graph Colorings

摘要： 图着色和团覆盖问题在组合优化中是核心挑战。这两个问题都被证明是 NP-难的，因此在最坏情况下计算上难以处理。一个著名的用于计算这些问题近似解的方法是洛瓦兹θ函数$\vartheta(G)$，它被定义为半定规划（SDP）的解，因此可以有效地计算。 在这项工作中，我们超越了最坏情况下的分析，试图理解洛瓦兹θ函数是否能够恢复具有潜在团覆盖结构的随机实例的团覆盖，可能受到噪声的干扰。我们对此问题给出了肯定的回答，并证明了对于我们在本研究中引入的种植团模型生成的图，$\vartheta(G)$的 SDP 形式有唯一解，且以高概率揭示出底层的团覆盖结构。主要的技术步骤是证明了一个基于适当稀疏性概念的确定性恢复条件。 显示英文摘要

摘要： 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\'asz 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\'asz 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.