Next: MINIMUM DOMINATING SET Up: Covering and Partitioning Previous: Covering and Partitioning Index

### MINIMUM VERTEX COVER

- INSTANCE: Graph .

- SOLUTION: A vertex cover for G, i.e., a subset such that, for each edge , at least one of u and v belongs to V'.

- MEASURE: Cardinality of the vertex cover, i.e., |V'|.

- Good News: Approximable within [360] and [57].

- Bad News: APX-complete [371].

- Comment: Transformation from bounded MAXIMUM 3-SATISFIABILITY. Not approximable within 1.1666 [226]. Admits a PTAS for planar graphs [50] and for unit disk graphs [249]. The good news hold also for the weighted version [57], in which each vertex has a nonnegative weight and the objective is to minimize the total weight of the vertex cover. The weighted version admits a PTAS for planar graphs [50]. The case when degrees are bounded by is APX-complete [371] and [9] and not approximable within 1.1666 for a sufficiently large [110]. For it is approximable within 7/6 [69], for general within [209], and for not within 1.0029 [70]. Approximable within 3/2 for 6-claw-free graphs (where no independent set of size 6 exists in any neighbour set to any vertex) [209]. Variation in which is APX-complete [110] and approximable within . Approximable within if every vertex has degree at least [282] and [279].

  The generalization to k-hypergraphs, for , is approximable within k [56] and [229], which holds also in the weighted case. If the vertex cover is required to induce a connected graph, the problem is approximable within 2 [406]. 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 [26].

  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 for some [452]. 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 [84] and does not admit a PTAS [378].

- Garey and Johnson: GT1

Next: MINIMUM DOMINATING SET Up: Covering and Partitioning Previous: Covering and Partitioning Index