Next: Subgraphs and Supergraphs
Up: Covering and Partitioning
Previous: MINIMUM EDGE DISJOINT CYCLE
  Index
- 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
.
Viggo Kann
1999-04-22