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