Bad News:
There is no polynomial-time algorithm with relative error less than 1.5
[381].
Comment:
The negative result is obtained by relating the problem with the coloring
problem.
Solvable in polynomial time for planar graphs.
Observe that any graph has a cut cover of cardinality
.