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

• Good News: Approximable within [380] and [62] and [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 is APX-complete [393] and [9], for not approximable within 1.0029 [76], and not approximable within 1.1666 for a sufficiently large [118]. For it is approximable within 7/6 [75], and for general within [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 for p+1-claw-free graphs [232]. Variation in which is APX-complete [118], and is approximable within [382]. Approximable within if every vertex has degree at least [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 and , for large values of n and [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 for some [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

Next: MINIMUM DOMINATING SET Up: Covering and Partitioning Previous: Covering and Partitioning   Index
Viggo Kann
2000-03-20