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