S
OLUTION
:
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
.
M
EASURE
:
Cardinality of the complete bipartite subgraph cover, i.e., the number of
subsets
.
Good News:
Approximable within
O(f(|V|))
if M
AXIMUM
C
LIQUE
is
approximable within
f(|V|)
[
150
].
Bad News:
Not approximable within
for some
[
264
].
Comment:
Equivalent to M
INIMUM
C
LIQUE
P
ARTITION
under ratio-preserving reduction
[
324
].