Next: MINIMUM VERTEX DISJOINT CYCLE
Up: Covering and Partitioning
Previous: MINIMUM CLIQUE COVER
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A complete bipartite subgraph cover for G, i.e., a collection
of subsets of V, such that each Vi induces
a complete bipartite subgraph of G and such that for each edge
there is some Vi that contains both u and v.
- MEASURE:
Cardinality of the complete bipartite subgraph cover, i.e., the number of
subsets Vi.
- Good News:
Approximable within O(f(|E|)) if MINIMUM CLIQUE PARTITION is
approximable within f(|V|) [208].
- Bad News:
See MINIMUM CLIQUE PARTITION.
- Comment:
Equivalent to MINIMUM CLIQUE PARTITION under ratio-preserving reduction
[421].
- Garey and Johnson: GT18
Viggo Kann
1999-04-22