- INSTANCE: Graph .
- SOLUTION:
A complete bipartite subgraph cover for
*G*, i.e., a collection of subsets of*V*, such that each induces a complete bipartite subgraph of*G*and such that for each edge there is some that contains both*u*and*v*. - MEASURE:
Cardinality of the complete bipartite subgraph cover, i.e., the number of
subsets .

*Good News:*Approximable within if MINIMUM CLIQUE PARTITION is approximable within [221].*Bad News:*See MINIMUM CLIQUE PARTITION.*Comment:*Equivalent to MINIMUM CLIQUE PARTITION under ratio-preserving reduction [444].*Garey and Johnson:*GT18