for even k
for odd k
 and .
On directed graphs the problem is approximable within 1.61 for k=1
, within 2 for ,
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 .
Admits a PTAS for complete Euclidean graphs .