Here we consider the weighted vertex cover problem. Suppose the graph in Figure 8.23 represents an instance of vertex cover in which the cost of having vertex i in S is w(i) = (i –2)² + 1 for i = 1, 2, 3, 4, 5. For example, if v₄ is in S, we must use w (4) = (4 –2)² + 1 = 5 units of our resource. Now, rather than minimizing the number of vertices in S, we seek a solution that minimizes the total amount of resource used ∑_iєS w(i). Using our analogy of soldiers guarding intersections, you can think of w(i) as a description of the number of soldiers needed to guard intersection i . Given the graph in Figure 8.23 and the weighting function w (i) = (i –2)² + 1, find a minimum-cost weighted vertex cover.

Figure 8.23