Fooling strong LP and SDP relaxations for VERTEX COVER
Scribes: Pierre Pansu and Claire Mathieu
The problem: VERTEX COVER
- Input: a graph.
- Output: a set of vertices touching all edges.
- Objective: minimize size
Dinur Safra: -inapproximable assuming PNP.
KR: -inapproximable assuming UGC.
Typical approximation algorithms: solve a relaxation, round the solution to make it a true vertex cover. Typical analysis: compare the cost of the rounded solution to the cost fot the solution to the relaxation.
1. The standard linear programming (LP) relaxation
Exact formulation (Integer Program, intractable): takes value or . Minimize under constraints for each edge .
Standard LP relaxation (Linear Program, polynomial-time solvable) consists in replacing “ or ” by .
Integrality gap is the maximum over all vertex graphs of the ratio of the value of the IP over the value of the LP. For algorithms that first solve a relaxation, then round it to a solutino of the original problem, the analysis is always done by relating the value of the output to the value of the relaxation, and so, even if the rounding is wonderful, the proof shows that such an algorithm has an approximation ratio that, at best, equals the integrality gap. Hence the interest in evaluating integrality gaps.
The above LP relaxation has an integrality ratio of almost 2, in fact, of , achieved by the -vertex clique. This means that, using this LP to design an approximtion algorithm, no matter what the rounding, we cannot hope for an approximation ratio better than . We say that this LP relaxation is fooled by cliques. Goemans Kleinberg 1995.
2. The standard semi-definite programming (SDP) relaxation
If encodes “belongs to vertex cover”, then for each vertex , or not. Exact formulation: Minimize under constraints for all , , and, for all edges ,
Standrad SDP relaxation (semi-definite program, essentially polynomial-time solvable) consists in replacing numbers (one-dimensional vectors) ‘s by vectors (no constraints on dimensions — may have dimensions).
This SDP relaxation is not fooled by cliques but the integrality gap is still . The integrality gap is reached for Frankl-Rödl graphs. These graphs are parametrized by . Vertices are , edges connect vertices at Hamming distance . For , each vertex has exactly one edge, to the antipodal vertex, and we get a perfect matching, so there is a vertex cover of size . For we get the complete graph, and the minimum vertex cover has size . The Frankl-Rödl theorem says: fix . Then the minimum vertex cover has size .
Can we lower the integrality gap by using other, stronger LP or SDP relaxations? That would give hope that there exists a better-than-2 approximation algorithm.
3. Stronger relaxations: -gonal inequalities
Change the SDP relaxation by putting in additional inequalities (constraints). Use the metric induced by . In an ideal world, vectors live in dimension and integral solutions induce cut metrics, so if we add inequalities that are valid for cut metrics, it’s still a relaxation of the exact problem. For example, the -gonal inequalities: take a set of vertices of odd size , consisting of a subset of size and a subset *B* of size : the inequality is valid and can be added to the SDP relaxation. This creates a stronger SDP relaxation. What happens to the integrality gap?
Georgiou at al. 2009 : Even with -gonal inequalities, the integrality gap is still . (Charikar 2002 had shown that for -gonal inequalities). On what graph is the integrality gap reached? Still Frank-Rodl. How does the proof go? Given a polynomial with positive coefficients, define tensor algebra of . Then . Applying this to the function gives a solution to the stronger SDP with value close to .
4. Stronger relaxations: Lovasz-Schrijver, Sherali-Adams and Lasserre hierarchies
Level Sherali-Adams applied to an LP relaxation produces a distribution on vertex covers which has the following property: it has one variable for each subset of at most vertices and each assignment of 0s and 1s to the vertices of ( means that vertex is in the vertex cover). It has constraints expressing the fact that is a distribution of vertex covers on the subgraph induced by . It has constraitns expressing the fact that abd must be consistent distributions, i.e. have the same marginal distribution over the intersection of and . When this is the standard LP relaxation, when this is a stronger LP relaxation (polynomial-time solvable for bounded). What happens to the integrality gap? It’s still even for . It is 1 for .
What about combining the powers of Sherali-Adams and of SDPs? The standard SDP relaxation constrqints can be rewritten as: for all , , positive semi-definite matrix, and, for all edges ,
For consistency between the Sherali-Adams solution and the SDP solution we can add the constraint . That’s the “Sherali-Adams SDP version”. What happens to the integrality gap? For , still . What graph provides the proof? Still the Frank-Rodl graph.
There are other hierarchies also depending on (solvable in runtime exponential in ) and relations between them, comparing their relative strength in terms of reducing the integrality gap. None has a proved integrality gap less than except when is at least .