資料結構與演算法

(30 points) A vertex cover of an undirected graph $G = (V, E)$ is a subset $V' \subseteq V$ such that if $(u, v) \in E$, then either $u \in V'$ or $v \in V'$ (or both). The size of a vertex cover is defined as the number of vertices in it. The vertex-cover problem is to find a vertex cover of minimum size in a given undirected graph. It has been shown to be NP-hard, thus we cannot find a polynomial-time algorithm for solving it exactly unless $\text{NP} = \text{P}$. Fortunately, some polynomial-time approximation algorithms have been proposed for solving the vertex-cover problem.

The following two approximation algorithms take as input an undirected graph and compute a vertex cover for it. Initially, all edges in the graph are uncovered for both Algorithm VC-Arbitrary and Algorithm VC-Max-Degree. Once a vertex $v$ is put into the cover, all edges incident on $v$ are covered and removed.

• Algorithm VC-Arbitrary picks an arbitrary uncovered edge $(u, v)$, puts both $u$ and $v$ into the cover, throws out all edges incident on either $u$ or $v$, and repeats the process until there are no uncovered edges left.
• Algorithm VC-Max-Degree picks a vertex $v$ that covers the most number of uncovered edges, puts $v$ into the cover, throws out all edges incident on $v$, and repeats the process until there are no uncovered edges left.

(a) (10 points) Give an example for which Algorithm VC-Arbitrary yields a solution that is at least double the size of a minimum-size vertex cover. Give another example for which Algorithm VC-Max-Degree will definitely yield a solution with the size more than that of a minimum-size vertex cover no matter how it breaks the tie. Each example should contain no more than ten vertices. You have to justify your solution by showing the vertex cover found by the algorithm and its corresponding minimum-size vertex cover.

(b) (10 points) Prove or disprove that Algorithm VC-Arbitrary has a smaller ratio bound than Algorithm VC-Max-Degree. The ratio bounds in your proof or disproof should be as tight as possible.

(c) (10 points) In the weighted vertex-cover problem, you are given an undirected graph $G = (V, E)$ and a weight $w(v)$ for each vertex $v \in V$, and the objective is to find a vertex cover (covering all edges in $E$) of minimum total weight. In other words, the goal is to find a vertex cover $C$ of $G$ such that $\sum_{v \in C} w(v)$ is minimized among all possible vertex covers of $G$. You are required to formulate the weighted vertex cover problem as an integer linear program.