Next: Subgraphs and Supergraphs Up: Covering and Partitioning Previous: MINIMUM EDGE DISJOINT CYCLE Index

### MINIMUM CUT COVER

- INSTANCE: Graph .

- SOLUTION: A collection of cuts, i.e., a collection of subsets such that, for each edge , a subset Vi exists such that either and or and .

- MEASURE: Cardinality of the collection, i.e., m.

- Good News: Approximable within [361].

- Bad News: There is no polynomial-time algorithm with relative error less than 1.5. [361].

- 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 .