Consider again the graph in Figure 8.36. Now suppose that the cost of placing a vertex in S varies. Suppose the cost of placing vertex i in S is g(i) = (–i² + 6i –5)³ for i є {1, 2, 3, 4, 5}. Repeat parts (a), (b), and (c) of the previous problem for this new version of the problem. This is an instance of weighted vertex cover.

Figure 8.36

Data from Previous problem 

a. Find a minimum vertex cover in the graph in Figure 8.36.

b. Formulate an integer program to find a minimum vertex cover in the graph in Figure  8.36.
c. Solve the integer program in part (b) with computer software.