Skip to content

35.1 The vertex-cover problem


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



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


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.)

Consider a bibartite graph with left part $L$ and right part $R$ such that $L$ has $5$ vertices of degrees $(5, 5, 5, 5, 5)$ and $R$ has $11$ vertices of degrees $(5, 4, 4, 3, 2, 2, 1, 1, 1, 1, 1)$ (the graph is easy to draw and the figure is omitted here).

Clearly there exists a vertex-cover of size $5$ (the left vertices). The idea is to show that the proposed algorithm chooses all the vertices on the right part, resulting in the approximation ratio of $11 / 5 > 2$.

  1. After choosing the first vertex in $R$, the degrees on $L$ decrease to $(4, 4, 4, 4, 4)$.
  2. After choosing the second vertex in $R$, the degrees on $L$ decrease to $(4, 3, 3, 3, 3)$.
  3. After choosing the third vertex in $R$, the degrees on $L$ decrease to $(3, 3, 2, 2, 2)$.
  4. After choosing the fourth vertex in $R$, the degrees on $L$ decrease to $(2, 2, 2, 2, 1)$.
  5. After choosing the fifth vertex in $R$, the degrees on $L$ decrease to $(2, 2, 1, 1, 1)$.
  6. After choosing the sixth vertex in $R$, the degrees on $L$ decrease to $(1, 1, 1, 1, 1)$.

Now the algorithm still has to choose $5$ more vertices.


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



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.