The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs.
Siavosh Benabbas, Konstantinos Georgiou, Avner Magen · Electronic colloquium on computational complexity · 2010
We study the performance of the Sherali-Adams system for VERTEX COVER on graphs with vector chromatic number 2 + . We are able to construct solutions for LPs derived by any number of SheraliAdams tightenings by introducing a new tool to establish Local-Global Discrepancy. When restricted to Θ(1/ ) 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 [GK98] 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 SheraliAdams SDPs.