Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR10-169 | 8th April 2011 05:27

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs

RSS-Feed




Revision #2
Authors: Siavosh Benabbas, Siu On Chan, Konstantinos Georgiou, Avner Magen
Accepted on: 8th April 2011 05:27
Downloads: 2355
Keywords: 


Abstract:

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.



Changes to previous version:

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.


Revision #1 to TR10-169 | 13th February 2011 01:43

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs


Abstract:

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.



Changes to previous version:

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.


Paper:

TR10-169 | 10th November 2010 21:20

The Sherali-Adams System Applied to Vertex Cover: Why Borsuk Graphs Fool Strong LPs and some Tight Integrality Gaps for SDPs





TR10-169
Authors: Siavosh Benabbas, Konstantinos Georgiou, Avner Magen
Publication: 10th November 2010 21:26
Downloads: 2737
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint