跳转至

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

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.

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

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用