Comment:
Approximable within
for even k
and within
for odd k
[109] and [161].
On directed graphs the problem is approximable within 1.61 for k=1
[317], within 2 for ,
and within
for
[109].
Variation in which each edge has a nonnegative weight and the
objective is to minimize the total weight of the spanning subgraph is
approximable within 2 for every k [320].
Admits a PTAS for complete Euclidean graphs [130].