A semidefinite approach to the K-i-cover problem

作者：Gouveia Joao; Pfeiffer James^*

来源：Operations Research Letters, 2014, 42(2): 156-160.

DOI：10.1016/j.orl.2014.01.003

• Sums of squares relaxations
• Theta bodies
• Minimal K-i-cover problem
• Maximal K-i-free subgraph problem
• Tuza's conjecture

We apply theta body relaxations to the K-i-cover problem and 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.

• 出版日期2014-3