In which we show how to use linear programming to approximate the vertex cover problem.
1. Linear Programming Relaxations
An integer linear program (abbreviated ILP) is a linear program (abbreviated LP) with the additional constraints that the variables must take integer values. For example, the following is an ILP:
Where is the set of natural numbers. The advantage of ILPs is that they are a very expressive language to formulate optimization problems, and they can capture in a natural and direct way a large number of combinatorial optimization problems. The disadvantage of ILPs is that they are a very expressive language to formulate combinatorial optimization problems, and finding optimal solutions for ILPs is NP-hard.
If we are interested in designing a polynomial time algorithm (exact or approximate) for a combinatorial optimization problem, formulating the combinatorial optimization problem as an ILP is useful as a first step in the following methodology (the discussion assumes that we are working with a minimization problem):
- Formulate the combinatorial optimization problem as an ILP;
- Derive a LP from the ILP by removing the constraint that the variables have to take integer value. The resulting LP is called a “relaxation” of the original problem. Note that in the LP we are minimizing the same objective function over a larger set of solutions, so ;
- Solve the LP optimally using an efficient algorithm for linear programming;
- If the optimal LP solution has integer values, then it is a solution for the ILP of cost , and so we have found an optimal solution for the ILP and hence an optimal solution for our combinatorial optimization problem;
- If the optimal LP solution has fractional values, but we have a rounding procedure that transforms into an integral solution such that for some constant , then we are able to find a solution to the ILP of cost , and so we have a -approximate algorithm for our combinatorial optimization problem.
In this lecture and in the next one we will see how to round fractional solutions of relaxations of the Vertex Cover and the Set Cover problem, and so we will be able to derive new approximation algorithms for Vertex Cover and Set Cover based on linear programming.
2. The Weighted Vertex Cover Problem
Recall that in the vertex cover problem we are given an undirected graph and we want to find a minimum-size set of vertices that “touches” all the edges of the graph, that is, such that for every at least one of or belongs to .
We described the following 2-approximate algorithm:
- Input:
- For each
- if then
- return
The algorithm finds a vertex cover by construction, and if the condition in the if step is satisfied times, then and the graph contains a matching of size , meaning that the vertex cover optimum is at least and so is at most twice the optimum. Consider now the weighted vertex cover problem. In this variation of the problem, the graph comes with costs on the vertices, that is, for every vertex we have a non-negative cost , and now we are not looking any more for the vertex cover with the fewest vertices, but for the vertex cover of minimum total cost . (The original problem corresponds to the case in which every vertex has cost 1.)
Our simple algorithm can perform very badly on weighted instances. For example consider the following graph:
Then the algorithm would start from the edge , and cover it by putting into . This would suffice to cover all edges, but would have cost , which is much worse than the optimal solution which consists in picking the vertices , with a cost of .
Why does the approximation analysis fail in the weighted case? In the unweighted case, every edge which is considered by the algorithm must cost at least 1 to the optimum solution to cover (because those edges form a matching), and our algorithm invests a cost of 2 to cover that edge, so we get a factor of 2 approximation. In the weighted case, an edge in which one endpoint has cost 1 and one endpoint has cost 100 tells us that the optimum solution must spend at least 1 to cover that edge, but if we want to have both endpoints in the vertex cover we are going to spend 101 and, in general, we cannot hope for any bounded approximation guarantee.
We might think of a heuristic in which we modify our algorithm so that, when it considers an uncovered edge in which one endpoint is much more expensive than the other, we only put the cheaper endpoint in . This heuristic, unfortunately, also fails completely: imagine a “star” graph like the one above, in which there is a central vertex of cost 100, which is connected to 10,000 other vertices, each of cost 1. Then the algorithm would consider all the 10,000 edges, and decide to cover each of them using the cheaper endpoint, finding a solution of cost 10,000 instead of the optimal solution of picking the center vertex, which has cost 100.
Indeed, it is rather tricky to approximate the weighted vertex cover problem via a combinatorial algorithm, although we will develop (helped by linear programming intuition) such an approximation algorithm by the end of the lecture.
Developing a 2-approximate algorithm for weighted vertex cover via a linear programming relaxation, however, is amazingly simple.
3. A Linear Programming Relaxation of Vertex Cover
Let us apply the methodology described in the first section. Given a graph and vertex costs , we can formulate the minimum vertex cover problem for as an ILP by using a variable for each vertex , taking the values 0 or 1, with the interpretation that means that , and means that . The cost of the solution, which we want to minimize, is , and we want for each edge . This gives the ILP
Next, we relax the ILP (2) to a linear program.
Let us solve the linear program in polynomial time, and suppose that is an optimal solution to the LP (3); how do we “round” it to a 0/1 solution, that is, to a vertex cover? Let’s do it in the simplest possible way: round each value to the closest integer, that is, define if , and if . Now, find the set corresponding to the integral solution , that is and output it. We have:
- The set is a valid vertex cover, because for each edge it is true that , and so at least one of or must be at least , and so at least one of or belongs to ;
- The cost of is at most twice the optimum, because the cost of is
And that’s all there is to it! We now have a polynomial-time 2-approximate algorithm for weighted vertex cover.
4. The Dual of the LP Relaxation
The vertex cover approximation algorithm based on linear programming is very elegant and simple, but it requires the solution of a linear program. Our previous vertex cover approximation algorithm, instead, had a very fast linear-time implementation. Can we get a fast linear-time algorithm that works in the weighted case and achieves a factor of 2 approximation? We will see how to do it, and although the algorithm will be completely combinatorial, its analysis will use the LP relaxation of vertex cover.
How should we get started in thinking about a combinatorial approximation algorithm for weighted vertex cover?
We have made the following point a few times already, but it is good to stress it again: in order to have any hope to design a provably good approximation algorithm for a minimization problem, we need to have a good technique to prove lower bounds for the optimum. Otherwise, we will not be able to prove that the optimum is at least a constant fraction of the cost of the solution found by our algorithms.
In the unweighted vertex cover problem, we say that if a graph has a matching of size , then the optimum vertex cover must contain at least vertices, and that’s our lower bound technique. We have already seen examples in which reasoning about matchings is not effective in proving lower bound to the optimum of weighted instances of vertex cover.
How else can we prove lower bounds? Well, how did we establish a lower bound to the optimum in our LP-based 2-approximate algorithm? We used the fact that the optimum of the linear programming relaxation (3) is a lower bound to the minimum vertex cover optimum. The next idea is to observe that the cost of any feasible solution to the dual of (3) is a lower bound to the optimum of (3), by weak duality, and hence a lower bound to the vertex cover optimum as well.
Let us construct the dual of (3). Before starting, we note that if we remove the constraints we are not changing the problem, because any solution in which some variables are larger than 1 can be changed to a solution in which every is at most one while decreasing the objective function, and without contradicting any constraint, so that an optimal solution cannot have any larger than one. Our primal is thus the LP in standard form
Its dual has one variable for every edge , and it is
That is, we want to assign a nonnegative “charge” to each edge, such that the total charge over all edges is as large as possible, but such that, for every vertex, the total charge of the edges incident on the vertex is at most the cost of the vertex. From weak duality and from the fact that (4) is a relaxation of vertex cover, we have that for any such system of charges, the sum of the charges is a lower bound to the cost of the minimum vertex cover in the weighted graph with weights .
Example 1 (Matchings) Suppose that we have an unweighted graph , and that a set of edges is a matching. Then we can define if and if . This is a feasible solution for (5) of cost .
This means that any lower bound to the optimum in the unweighted case via matchings can also be reformulated as lower bounds via feasible solutions to (5). The latter approach, however, is much more powerful.
Example 2 Consider the weighted star graph from Section 2. We can define for each vertex , and this is a feasible solution to (5). This proves that the vertex cover optimum is at least 5.
5. Linear-Time 2-Approximation of Weighted Vertex Cover
Our algorithm will construct, in parallel, a valid vertex cover , in the form of a valid integral solution to the ILP formulation of vertex cover (2), and a feasible solution to the dual (5) of the linear programming relaxation, such that the cost of is at least half the cost . Before starting, it is helpful to reformulate our old algorithms in this language
- Input: undirected, unweighted, graph
- for each edge
- if and then
- if and then
- return
Our goal is to modify the above algorithm so that it can deal with vertex weights, while maintaining the property that it finds an integral feasible and a dual feasible such that . The key property to maintain is that when we look at the edge , and we find it uncovered, what we are going to “spend” in order to cover it will be at most , where will be a charge that we assign to without violating the constraints of (5).
We will get simpler formulas if we think in terms of a new set of variables , which represent how much we are willing to “pay” in order to put in the vertex cover; at the end, if then the vertex is selected, and , and if then we are not going to use in the vertex cover. Thus, in the integral solution, we will have , and so and so the total amount we are willing to pay, is an upper bound to the cost of the integral solution .
Initially, we start from the all-zero dual solution and from no commitment to pay for any vertex, . When we consider an edge , if or , we have committed to pay for at least one of the endpoints of , and so the edge will be covered. If and , we need to commit to pay for at least one of the endpoints of the edge. We need to pay an extra to make sure is in the vertex cover, or an extra to make sure that is. We will raise, and here is the main idea of the algorithm, both the values of and by the smallest of the two values. This will guarantee that we cover by “fully funding” one of the endpoints, but it will also put some extra “funding” into the other vertex, which might be helpful later. We also set to .
Here is the psedocode of the algorithm:
- Input: undirected, unweighted, graph
- for each edge
- if and then
- if and then
- return
The algorithm outputs a correct vertex cover, because for each edge , the algorithm makes sure that at least one of or is true, and so at least one of or belongs to at the end.
Clearly, we have
Next, we claim that the vector at the end of the algorithm is a feasible solution for the dual (5). To see this, note that, for every vertex ,
because initially all the and all the are zero, and when we assign a value to a variable we also simultaneously raise and by the same amount. Also, we have that, for every vertex
by construction, and so the charges satisfy all the constraints
and define a feasible dual solution. We then have
by weak duality. Finally, every time we give a value to a variable, we also raise the values of and by the same amount, and so the sum of our payment commitments is exactly twice the sum of the charges
Putting all together we have
and we have another 2-approximate algorithm for weighted vertex cover!
It was much more complicated than the simple rounding scheme applied to the linear programming optimum, but it was worth it because now we have a linear-time algorithm, and we have understood the problem quite a bit better.