Exercise 3 (2 pts). The MIN VERTEX COVER problem can be solved using the approxi- mation algorithm described in the textbook (section 35.1) and in the slides. Apply this algorithm to the graph in Figure 1. Figure 1: Instance of MIN VERIEX COVEIR for Exereise 3 1. Give a trace of the algorithm on this instance such that the result is a vertex cover of size 6. Note that the algorithm does not specify exactly how to pick an edge if there is more than one choice. In this case, you can pick any edge untouched by any marked edge e: 5 6 7 8 Exercise 3 (2 pts). The MIN VERTEX COVER problem can be solved using the approxi- mation algorithm described in the textbook (section 35.1) and in the slides. Apply this algorithm to the graph in Figure 1. Figure 1: Instance of MIN VERIEX COVEIR for Exereise 3 1. Give a trace of the algorithm on this instance such that the result is a vertex cover of size 6. Note that the algorithm does not specify exactly how to pick an edge if there is more than one choice. In this case, you can pick any edge untouched by any marked edge e: 5 6 7 8