Comment:
Admits a PTAS if every vertex has degree
[39].
It remains APX-complete even if
is fixed.
For
and
it is approximable within 4/3 and 12/7,
respectively.
In the case of directed graphs the problem is approximable within 2 [383]
and is APX-hard [188].
The vertex deletion variation is approximable within
and is
APX-complete [188].