4810-1183 Approximation and Online Algorithms
Lecture Note 4: Approximation Algorithm for Vertex Cover Problem
Introduction
On last week, we have introduced you an approximation algorithm for the knapsack problem. The algorithm
looks very close to a greedy algorithm, an algorithmic paradigm where we will pick items in order of some“good” function until we cannot pick an item anymore. However, it is not exactly a greedy algorithm. At
the end of the algorithm, we choose between two sets of strawberries. Actually, many approximation
algorithms are devised based on that paradigm. We usually get an approximation algorithm by slightly
modifying a greedy algorithm.
The greedy-algorithm-based is one of the two most common schemes for approximation algorithm,
and we will study the other common scheme today. The scheme is called as deterministic rounding.
Vertex Cover
Let recall our discussion on social networks in Lecture Note 2. We have a set of persons 𝑉 and a set offriendships between two persons 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}. Suppose that we are spies from a particular country,and we want to track all information in a social network using social engineering. We will bribe a set ofpersons and make them reveal their communications with all friends. The bribing is very costly and wewant to minimize the number of persons whom we bribe.
The problem in the previous paragraph can be formulized into the following optimization models:
Input:

Set 𝑉, Set 𝐸 ⊆ {{𝑢, 𝑣}: 𝑢, 𝑣 ∈ 𝑉}

Output:Set 𝑆 ⊆ V (set of persons whom we bribe)

Objective Function:

Minimize |S|

Constraint:

For all {𝑢, 𝑣} ∈ 𝐸, 𝑢 ∈ 𝑆 or 𝑣 ∈ 𝑆Consider the above social network, where 𝑉 = {1,2,3,4} and 𝐸 = {{1,2}, {1,3}, {2,3}, {3,4}}. We can spy
all the information if we bribe 1 and 3, and it is not possible to cover all communications by just one person.
The optimal solution is 𝑆 ∗ = {1,3} and the optimal value is 𝑂𝑃𝑇 = 2.
Again, the optimization model is NP-hard. To solve the problem, let define new variables 𝑥𝑖 foreach 𝑖 ∈ 𝑉 . We have 𝑥𝑖 = 1 when 𝑖 ∈ 𝑆 , and 𝑥𝑖 = 0 otherwise. Suppose that 𝑉 = {1, … , 𝑛} . It is
straightforward to see that 𝑥1 , … , 𝑥𝑛 have an equivalent information with 𝑆. We can construct 𝑥1 , … , 𝑥𝑛
from 𝑆 and we can construct 𝑆 from 𝑥1 , … , 𝑥𝑛 . Because of that, we will output 𝐱 = [𝑥1 , … , 𝑥𝑛 ]t instead of𝑆.

Then, we have |𝑆| = ∑𝑖 𝑥𝑖 , because, to |𝑆|, 𝑖 contributes 1 = 𝑥𝑖 when 𝑖 ∈ 𝑆 and 0 = 𝑥𝑖 otherwise.
When 𝐜 = [1,1, … ,1]𝑡 , we have |𝑆| = 𝐜 𝑡 𝐱.
Consider the objective function of our optimization model. For all {𝑢, 𝑣} ∈ 𝐸, we want to have 𝑢 ∈𝑆 or 𝑣 ∈ 𝑆. We want to have 𝑥𝑢 = 1 or 𝑥𝑣 = 1. That is equivalent to have 𝑥𝑢 + 𝑥𝑣 = 1 or 𝑥𝑢 + 𝑥𝑣 = 2,and the conditions can be written as 𝑥𝑢 + 𝑥𝑣 ≥ 1. In our previous example, we want to have the following
conditions:𝑥1 + 𝑥2 ≥ 1
𝑥1 + 𝑥3 ≥ 1𝑥2 + 𝑥3 ≥ 1𝑥3 + 𝑥4 ≥ 1
The conditions can be rewritten to the following form:
1[10010100 0 𝑥1
11 0 ] [𝑥2 ] ≥ [1].
11 0 𝑥3
1 1 𝑥411 1 00
110
10When 𝐀 = [] and 𝐛 = [1], the condition is 𝐀𝐱 ≥ 𝐛. For the general case, we will have 𝐀 be a0 1 1 010 0 1 1
1|𝐸| × |𝑉| matrix where each row is corresponding to a friendship and each column is corresponding to aperson. At a row that is corresponding to a friendship {𝑢, 𝑣}, elements of 𝐀 is 1 only at the column ofpersons 𝑢, 𝑣. The elements will be 0 at the other columns. The vector 𝐛 is always be [1, 1, … , 1]𝑡 .
By the notations above, we can reformulate our optimization model to the following:
Input:

Matrix 𝐀, Vector 𝐛, 𝐜Assumption: At each row of 𝐴, two of the elements are 1.
The other elements are 0. All elements of 𝐛, 𝐜 are 1.

Output:Vector 𝐱 (all elements are 0 or 1)

Objective Function:

Minimize 𝐜 𝑡 𝐱

Constraint:𝐀𝐱 ≥ 𝐛The optimization model looks very close to linear programming. One might think that we can solve theoptimization model using library like CPLEX®. There is only one difference: we require that 𝑥𝑖 must be 0or 1, but that difference makes us cannot use CPLEX® to solve the problem. Consider the previous example
again. If we use CPLEX® to solve the problem without the conditions on 𝑥𝑖 , the output could be 𝑥1 = 𝑥2 =𝑥3 = 𝑥4 = 0.5. We know how to construct 𝑆 from 𝐱 when all 𝑥𝑖 are 0 or 1, but we do not how to do thatwhen 𝑥𝑖 is not that 2 numbers.
Rounding
Now, let us consider the following optimization model, and call the problem as “fractional vertex cover”.

Input:Matrix 𝐀, Vector 𝐛, 𝐜Assumption: At each row of 𝐴, two of the elements are 1.
The other elements are 0. All elements of 𝐛, 𝐜 are 1.

Output:Vector 𝐱 (𝟎 ≤ 𝒙𝒊 ≤ 𝟏 for all 𝒊)

Objective Function:

Minimize 𝐜 𝑡 𝐱

Constraint:𝐀𝐱 ≥ 𝐛Instead of having 𝑥𝑖 ∈ {0,1}, we have 𝑥𝑖 ∈ [0,1]. Although a library for linear programming cannot solve
our optimization models when the outputs must be within a discrete set, it theoretically works very wellwhen the outputs must be within a single continuous set. Because of that, we can use a library for linear
programming to solve the “fractional vertex cover”.
Our algorithm is as follows:
1: Use a library for linear programming to solve the“fractional vertex cover”. Suppose that the output is 𝐱 = (𝑥1 , … , 𝑥𝑛 ).
2: For all 𝑖, let 𝑥𝑖′ = 1 when 𝑥𝑖 ≥ 0.5, and 𝑥𝑖 = 0 otherwise.
Let 𝐱 ′ = (𝑥1′ , … , 𝑥𝑛′ ).
3: Return 𝑥′ as an answer of the vertex cover problem.
We will prove the correctness of the above algorithm in the previous theorem.
Theorem 1 An output of the algorithm 𝐱′ satisfies the constraint of vertex cover problem.
Proof: Because the vector 𝐱 is a solution of the fractional vertex cover problem, we know that, for {𝑢, 𝑣} ∈𝐸,𝑥𝑢 + 𝑥𝑣 ≥ 1.
By the above inequality, we know that either 𝑥𝑢 or 𝑥𝑣 is not smaller than 0.5. If both of them are smaller,
we will never have the summation larger than 1. By the rounding at line 2 of the algorithm, we know thateither 𝑥𝑢′ or 𝑥𝑣′ are 1. For all {𝑢, 𝑣} ∈ 𝐸, we have 𝑥𝑢′ + 𝑥𝑣′ ≥ 1, which means that 𝐱′ satisfies the constraintof the vertex cover problem.
∎Let 𝑆𝑂𝐿 be the objective value of the output from our algorithm, denoted by 𝐱 ′ , let 𝑂𝑃𝑇 be theoptimal value, and 𝐱 ∗ be the optimal solution.
We have the following theorem for the algorithm in the previous paragraph.
Theorem 2 For any particular input, 𝑆𝑂𝐿 ≤ 2 ⋅ 𝑂𝑃𝑇.
Proof: Let 𝐱 = (𝑥1 , … , 𝑥𝑛 ) be the optimal solution for the fractional vertex cover problem. It is the vector
in [0,1]𝑛 that minimizes 𝐜 𝑡 𝐱 when 𝐀𝐱 ≥ 𝐛. On the other hand, 𝐱 ∗ is the vector in {0,1}𝑛 that minimizes the𝐜 𝑡 𝐱 when 𝐀𝐱 ≥ 𝐛. Both of the vectors minimize the objective function with the same constraint, but 𝐱 isselected from a larger set. 𝐱 has more chance to minimizes the objective function. The objective value of 𝐱
is better (thus smaller) than 𝐱 ∗ , i.e. 𝐜 𝑡 𝐱 ≤ 𝐜 𝑡 𝐱 ∗.

Now, let consider the value of 𝑥𝑖′ . By the “rounding” at Line 2 of the algorithm, we have 𝑥𝑖′ ≤ 2 ⋅𝑥𝑖 . Then,
𝑆𝑂𝐿 = 𝐜 𝑡 𝐱′ = ∑ 𝑥𝑖′ ≤ 2 ⋅ ∑ 𝑥𝑖 = 2 ⋅ 𝐜 𝑡 𝐱 ≤ 2 ⋅ 𝐜 𝑡 𝐱 ∗ = 2 ⋅ 𝑂𝑃𝑇.
𝑖𝑖∎
Approximation Algorithm for Minimization Problems
In the previous lecture note, we work on the knapsack problem. There, we tried to “maximize” ourhappiness from strawberries. From the algorithm, we cannot have the maximum happiness as in an optimalsolution, but we can prove 𝑆𝑂𝐿 ≥ 0.5 ⋅ 𝑂𝑃𝑇. An algorithm that can attain the inequality is called 0.5approximation algorithm.
In the vertex cover problem, we are trying to “minimize” our cost. We cannot have the minimum
cost as in an optimal solution. The objective value of our output, 𝑆𝑂𝐿, must be larger than 𝑂𝑃𝑇. However,we prove that 𝑆𝑂𝐿 is not larger than 2 ⋅ 𝑂𝑃𝑇. An algorithm that can attain that is called 2-approximation
algorithm.
We have 𝛼-approximation algorithm for both maximization and minimization problems. However,𝛼 < 1 for maximization problems and 𝛼 > 1 for minimization problems.
Network Monitoring Problem
Let consider a problem considered in [2]. Suppose again that we want to monitor all communications. Here,
we do not have to bribe persons anymore because we are ISP. We have all communications passing ourservers! However, it is quite costly to set up a monitoring tool at all servers, and we want to set up the tools
at as least as servers possible. Our servers are connected so well that a communication will pass only of our
two servers, ingress server (where the communication arrives) and forwarding server (where thecommunication is forwarded to other ISPs.
By the discussion at the previous paragraph, we have the following optimization model.
Input:

Number of servers 𝑛
Number of communications 𝑚
Ingress servers for each communication 𝐼1 , … , 𝐼𝑚
Forward servers for each communication 𝑂1 , … , 𝑂𝑚

Output:Servers to set the monitoring tools 𝑆 ⊆ {1, … , 𝑛}Constraint:

For all communications 𝑗, 𝐼𝑗 ∈ 𝑆 or 𝑂𝑗 ∈ 𝑆

Objective Function:

Minimize |𝑆|

The ingress and forward servers are equivalent in the above problem. Because of that, we candenote all information about a communication 𝑗 by {𝐼𝑗 , 𝑂𝑗 }, and restate the problem to the following way:
Input:

Set of servers 𝑉 = {1, … , 𝑛}
Set of communications 𝐸 = {{𝐼1 , 𝑂1 }, … , {𝐼𝑚 , 𝑂𝑚 }}Output:𝑆⊆𝑉

Constraint:

For all {𝐼𝑗 , 𝑂𝑗 } ∈ 𝐸, 𝐼𝑗 ∈ 𝑆 or 𝑂𝑗 ∈ 𝑆

Objective Function:

Minimize |𝑆|

The above optimization model is the vertex cover problem. We can use a 2-approximation algorithm tosolve the problem.
Exercises

Question 1: Consider the above social network. If we want to solve the vertex cover problem for thisnetwork, which linear program should we have?
Question 2: Modify the file .lp that you have made in Lecture 1 to have an LP in Question 1. Together withthe display file you have in Lecture 1, run CPLEX in the website
https://neos-server.org/neos/solvers/milp:CPLEX/LP.html
to check what is the optimal solution for the fractional vertex cover problem.
Question 3: From the optimal solution for the fractional vertex cover, what is our solution for the vertex
cover problem based on the deterministic rounding technique and your answer in Question 2? Is it anoptimal solution? If not, does it satisfy the inequality in Theorem 2?
Question 4: Repeat the same process for the social network in Page 1. Do you get an optimal solution for
the vertex cover by the deterministic rounding technique for the social network? If not, does your solution
satisfy the inequality in Theorem 2?
From the next question, consider the following situation:
We want to monitor all communications in the social network as always.
However, because monitoring all communications is too costly, we allow anumber communications to be unobserved. That number of communications isgiven as an input k (So, if we have 𝑚 communications in the social network, wewant to observe at least 𝑚 - k communications)
Question 5: State inputs of this problem by a mathematical formulation.
Question 6: State outputs of this problem by a mathematical formulation.
Question 7: State constraints of this problem by a mathematical formulation.
Question 8: State objective functions of this problem by a mathematical formulation.
Question 9: Write a program for solving vertex cover problem based on the fact that an efficientalgorithm for solving the optimization model in Questions 5 – 8 is given in a library.
[AnswerOf1_2] YourOptimizationModel([AnswerOf1_1]);

Sets VertexCover(Set V, Set E){//write your code for knapsack here}

Question 10: Discuss why your optimization model is NP-hard based on your answer of Question 9.
Question 11: Suppose that the number of unobserved communication is 1. What is the optimal solution
and optimal value for your optimization model when the social network is as follows?
14235From next question, we refer to a linear program such that an output 𝒙 must be a vector of integers as aninteger program. In other words, given matrix 𝑨, vector 𝒃, and vector 𝒄, we want to find an integer vector
𝒙 such that 𝑨𝒙 ≥ 𝒃 and 𝒄𝑡 𝒙 is minimized.
Question 2.2: Construct an integer program to solve an example in Question 2.1. What is matrix 𝑨, vector𝒃, and vector 𝒄 for this case? What is the optimal solution obtain from the linear program?
Question 2.3: Generalize Question 2.2. Give an idea how to construct matrix 𝑨, vector 𝒃, and vector 𝒄 froman arbitrary input of this problem. (You need not to really construct the matrix and vectors. Just give theidea how to construct them.)
From next question, we will consider your integer program in Question 2.3. However, we will not consider
the condition that 𝒙 has to be an integer vector.
Question 2.4: Consider the following social network. Suppose that the number of unobserved
communication is 1.

1

2

3

Explain why assigning 1/3 to all nodes in the output also provides a feasible solution to your linear program.
Question 2.5: Explain why deterministic rounding in the class does not work for this problem.
Question 2.6: Devise a deterministic rounding algorithm for this problem.
Hint: Your algorithm need not to be 2-approximation algorithm and you can consider the number ofunobserved communication during the rounding process.

References[1] D. P. Williamson and D. Shmoys, “The design of approximation algorithms”, Cambridge University
Press, 2011. Chapter 4[2] S. Agrawal, K. Naidu, and R. Rastogi, “Diagnosing link-level anomalies using passive probes”,
Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM 2007),
pages 1757-1765, 2007.