Linear programming relaxations of maxcut
Wenceslas Fernandez de la Vega, Claire M. Kenyon-Mathieu · 2007
It is well-known that the integrality gap of the usual linear programming relaxation for Maxcut is 2 − ǫ. For general graphs, we prove that for any ǫ and any fixed boundk, adding linear constraints of support bounded by k does not reduce the gap below 2−ǫ. We generalize this to prove that for any ǫ and any fixed bound k, strengthening the usual linear programming relaxation by doing k rounds of Sherali-Adams liftand-project does not reduce the gap below 2 − ǫ. On the other hand, we prove that for dense graphs, this gap drops to 1 + ǫ after adding all linear constraints of support bounded by some constant depending on ǫ.