Next: MINIMUM DOMINATING SET
Up: Covering and Partitioning
Previous: Covering and Partitioning
  Index
- 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