

35.1 The vertex-cover problem

35.1-1

Give an example of a graph for which $\text{APPROX-VERTEX-COVER}$ always yields a suboptimal solution.

(Omit!)

35.1-2

Prove that the set of edges picked in line 4 of $\text{APPROX-VERTEX-COVER}$ forms a maximal matching in the graph $G$.

(Omit!)

35.1-3 $\star$

Professor Bündchen proposes the following heuristic to solve the vertex-cover problem. Repeatedly select a vertex of highest degree, and remove all of its incident edges. Give an example to show that the professor's heuristic does not have an approximation ratio of $2$. ($\textit{Hint:}$ Try a bipartite graph with vertices of uniform degree on the left and vertices of varying degree on the right.)

(Omit!)

35.1-4

Give an efficient greedy algorithm that finds an optimal vertex cover for a tree in linear time.

(Omit!)

35.1-5

From the proof of Theorem 34.12, we know that the vertex-cover problem and the $\text{NP-complete}$ clique problem are complementary in the sense that an optimal vertex cover is the complement of a maximum-size clique in the complement graph. Does this relationship imply that there is a polynomial-time approximation algorithm with a constant approximation ratio for the clique problem? Justify your answer.

(Omit!)