Next: MINIMUM COMPLETE BIPARTITE SUBGRAPH Up: Covering and Partitioning Previous: MAXIMUM BALANCED CONNECTED PARTITION Index

### MINIMUM CLIQUE COVER

- 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