Next: MINIMUM COMPLETE BIPARTITE SUBGRAPH
Up: Covering and Partitioning
Previous: MAXIMUM BALANCED CONNECTED PARTITION
  Index
- INSTANCE:
Graph
.
- SOLUTION:
A clique cover for G, i.e., a collection
of
subsets of V, such that each Vi induces a complete subgraph
of G and such that for each edge
there is some Vi that
contains both u and v.
- MEASURE:
Cardinality of the clique cover, i.e., the number of subsets Vi.
- Good News:
Approximable within O(f(|E|)) if MINIMUM CLIQUE PARTITION is
approximable within f(|V|)
[208].
- Bad News:
Not approximable within g(|V|)2 unless MINIMUM CLIQUE PARTITION is
approximable within g(|V|).
- Comment:
Equivalent to MINIMUM CLIQUE PARTITION under ratio-preserving reduction
[322] and [421].
The complementary maximization problem, where |E| -k is to be maximized,
is approximable within 6/5 [130].
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
[452].
- Garey and Johnson: GT17
Next: MINIMUM COMPLETE BIPARTITE SUBGRAPH
Up: Covering and Partitioning
Previous: MAXIMUM BALANCED CONNECTED PARTITION
  Index
Viggo Kann
1999-04-22