- INSTANCE: Graph .
- SOLUTION: A collection of cuts, i.e., a collection of subsets such that, for each edge , a subset exists such that either and or and .
- MEASURE:
Cardinality of the collection, i.e.,
*m*.

*Good News:*Approximable within [381].*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 .