Tight Gaps for Vertex Cover in the Sherali-Adams SDP Hierarchy

Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou & Avner Magen
We give the first tight integrality gap for Vertex Cover in the Sherali-Adams SDP system. More precisely, we show that for every \epsilon >0, the standard SDP for Vertex Cover that is strengthened with the level-6 Sherali-Adams system has integrality gap 2-\epsilon. To the best of our knowledge this is the first nontrivial tight integrality gap for the Sherali-Adams SDP hierarchy for a combinatorial problem with hard constraints. For our proof we introduce a new...