We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to $O(1/ \epsilon)$ tightenings we show that the corresponding LP treats the input graph as a nearly perfect matching. Since there exist graphs with $2+o(1)$ vector chromatic number but no linear-sized independent sets, this immediately implies a tight integrality gap for superconstant levels of the Sherali-Adams system.
An important property of our solutions is that they can be slightly perturbed to also satisfy semidefinite conditions. In particular, using this approach we prove the first tight integrality gap for non trivial levels of the Sherali-Adams SDP system. Our argument reduces semidenifiteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level
SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is a valid for superconstant level Sherali-Adams SDPs.
We corrected a technical error that appeared in our first submission. In particular, the results that appear in the current revision subsume the claims of our initial submission TR10-169.
We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali- Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to $\Theta(1/\epsilon)$ tightenings we show that the corresponding LP treats the input graph as a nearly perfect matching. Since there exist graphs with $2+o(1)$ vector chromatic number but no linear-sized independent sets, this immediately implies a tight integrality gap for superconstant levels of the Sherali-Adams system.
An important property of our solutions is that they can be slightly perturbed to also satisfy semidefinite conditions. In particular, using this approach we give an alternative proof of the Goemans Kleinberg tight integrality gap for the standard SDP for VERTEX COVER. Our argument reduces semidenifiteness to a condition on the Taylor expansion of a reasonably simple function. For tight integrality gaps of non trivial levels of the Sherali-Adams SDP system we reduce semidenifiteness to the same condition on a more complicated function. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is valid for superconstant level Sherali-Adams SDPs.
A technical error in the previous version of the paper has been brought to our attention. In particular, there is was a gap in the proof of Lemma 8.2 (as presented in Section 11) and the Lemma itself is wrong for any odd value of parameter t. Although we believe that the Lemma holds for any even value of t (which would be enough for the purposes of our results) we do not have a proof of this statement yet. The updated manuscript contains the weaker results we can show using a weak version of the Lemma (which we prove), along with a conjecture about the stronger version of the Lemma.
Specifically, the following changes had to be applied to our results. Our first result, Theorem 1.1 (which formalizes our results advertised in the first paragraph of the abstract) still holds as its proof does not use the offending lemma. Our second result, Theorem 1.2 (which formalizes our results advertised in the second paragraph of the original abstract) however is reduced to a weaker theorem which only applies to level-2 of the Sherali-Adams SDP, as opposed to level-5.
We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector
chromatic number $2+\epsilon$. We are able to construct solutions for LPs derived by any number of Sherali-Adams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to
$O(1/ \epsilon)$ tightenings we show that the corresponding LP treats the input graph as a nearly perfect matching. Since there exist graphs with $2+o(1)$ vector chromatic number but no linear-sized independent sets, this immediately implies a tight integrality gap for superconstant levels of the Sherali-Adams system.
An important property of our solutions is that they can be slightly perturbed to also satisfy semidefinite conditions. In particular, using this approach we prove the first tight integrality gap for non trivial levels of the Sherali-Adams SDP system. Our argument reduces semidenifiteness to a condition on the Taylor expansion of a reasonably simple function that we are able to establish up to constant-level
SDP tightenings. We conjecture that this condition holds even for superconstant levels which would imply that in fact our solution is a valid for superconstant level Sherali-Adams SDPs.
