.
such that, for each
edge
, at least one of
u
and
v
belongs to
V'
.
[
275
] and [
37
].
on general
graphs [
37
] and admits a PTAS for planar graphs
[
33
].
Variation in which the degree of
G
is bounded by a constant
B
for
is A
PX
-complete [
284
] and [
4
] and not
approximable within 1.1666 for a sufficiently large
B
[
79
]. For
B=3
it is
approximable within 7/6
[
46
], for general
B
within
and within 3/2 for 6-claw-free graphs
(where no independent set of size 6 exists in any neighbour set to any
vertex) [
151
].
Variation in which the problem is restricted to `dense' graphs is
A
PX
-complete [
79
].
The generalization to
k
-hypergraphs, for
, is approximable within
k
[
166
].
If the vertex cover is required to induce a connected graph,
the problem is approximable within 2
[
14
].
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
[
14
].
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
[
352
].
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, does not admit a PTAS [
290
].
Viggo Kann