Bad News:
Not approximable within
,
for any
,
unless
[155].
Comment:
The problem is also approximable within ,
where
is the maximum degree, and is not approximable within
,
for any
under the same hypothesis.
The bad news also hold for split graphs and bipartite graphs.
The problem is approximable within 4 on circular-arc graphs [371].