Next: MINIMUM VERTEX DISJOINT CYCLE Up: Covering and Partitioning Previous: MINIMUM CLIQUE COVER Index

### MINIMUM COMPLETE BIPARTITE SUBGRAPH COVER

- 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