SOLUTION:
A clique cover for G, i.e., a collection
of
subsets of V, such that each
induces a complete subgraph
of G and such that for each edge
there is some
that
contains both u and v.
MEASURE:
Cardinality of the clique cover, i.e., the number of subsets .
Good News:
Approximable within
if MINIMUM CLIQUE PARTITION is
approximable within [221].
Bad News:
Not approximable within
unless MINIMUM CLIQUE PARTITION is
approximable within .
Comment:
Equivalent to MINIMUM CLIQUE PARTITION under ratio-preserving reduction
[338] and [444].
The constrained variation in which the input is extended with a positive
integer k, a vertex
and a subset S of V, and the problem
is to find the clique cover of size k that contains the largest number
of vertices from S, is not approximable within
for some
[476].