Bad News:
There is no polynomial-time algorithm with relative error less than 1.5.
[
276
].
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
.
.
of cuts, i.e., a collection of subsets
such that, for each edge
, a subset
exists
such that either
and
or
and
.
[
276
].
.