MINIMUM VERTEX COVER

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A vertex cover for G, i.e., a subset $V' \subseteq V$ such that, for each edge $(u,v) \in E$, at least one of u and v belongs to V'.
• MEASURE: Cardinality of the vertex cover, i.e., $\vert V'\vert$.

  
  

• Good News: Approximable within $2-\frac{\log\log\vert V\vert}{2\log\vert V\vert}$ [380] and [62] and $2-\frac{2\ln\ln\vert V\vert}{\ln\vert V\vert}(1-o(1))$ [232].
• Bad News: Not approximable within 1.1666 [242].
• Comment: The good news hold also for the weighted version [62,232], in which each vertex has a nonnegative weight and the objective is to minimize the total weight of the vertex cover. Admits a PTAS for planar graphs [53] and for unit disk graphs [264], even in the weighted case. The case when degrees are bounded by $\Delta\ge 3$ is APX-complete [393] and [9], for $\Delta=5$ not approximable within 1.0029 [76], and not approximable within 1.1666 for a sufficiently large $\Delta$ [118]. For $\Delta=3$ it is approximable within 7/6 [75], and for general $\Delta$ within $2-(1-o(1){2\log\log \Delta}/{\log \Delta}$ [232]. Approximable within 3/2 for 6-claw-free graphs (where no independent set of size 6 exists in any neighbour set to any vertex) [222], and within $2 - (1-o(1))2\log\log p/\log p$ for p+1-claw-free graphs [232]. Variation in which $\vert E\vert=\varepsilon \vert V\vert^2$ is APX-complete [118], and is approximable within $2 - 4\varepsilon /(13 + 4 \varepsilon )$ [382]. Approximable within $2/(1+\varepsilon )$ if every vertex has degree at least $\varepsilon \vert V\vert$ [297] and [294]. When generalized to k-uniform hypergraphs, the problem is equivalent to MINIMUM SET COVER with fixed number k of occurrences of each elements. Approximable within $k - (k-1)\ln\ln \vert V\vert/\ln \vert V\vert$ and $k - (k(k-1)\ln\ln \Delta)/\ln \Delta$, for large values of n and $\Delta$ [232]. If the vertex cover is required to induce a connected graph, the problem is approximable within 2 [429]. If the graph is edge-weighted, the solution is a closed walk whose vertices form a vertex cover, and the objective is to minimize the sum of the edges in the cycle, the problem is approximable within 5.5 [27]. The constrained variation in which the input is extended with a positive integer k and a subset S of V, and the problem is to find the vertex cover of size k that contains the largest number of vertices from S, is not approximable within $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ [476]. The maximization variation in which the input is extended just with a positive integer k, and the problem is to find k vertices that cover as many edges as possible, is 2-approximable [92] and does not admit a PTAS [400].
• Garey and Johnson: GT1