A semidefinite approach to the K_i-cover problem

Abstract

We apply theta body relaxations to the K_i-cover problem and use this to show polynomial time solvability for certain classes of graphs. In particular, we give an effective relaxation where all K_i-p-hole facets are valid, and study its relation to an open question of Conforti et al. For the triangle free problem, we show for K_n that the theta body relaxations do not converge by (n-2)/4 steps; we also prove for all G an integrality gap of 2 for the second theta body.