Next:
GT16 MINIMUM COMPLETE
Up:
Covering and Partitioning
Previous:
GT14 MINIMUM K-CAPACITATED
-
I
NSTANCE
:
Graph
.
-
S
OLUTION
:
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
.
-
M
EASURE
:
Cardinality of the clique 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
[
246
] and [
324
].
The complementary maximization problem, where
|E|-k
is to be maximized,
is approximable within 4/3 [
153
].
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
[
352
].
-
Garey and Johnson:
GT17
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997