MINIMUM CLIQUE COVER

• INSTANCE: Graph $G=\left(V,E\right)$.
• SOLUTION: A clique cover for G, i.e., a collection $V_1,V_2,\ldots,V_k$ of subsets of V, such that each $V_i$ induces a complete subgraph of G and such that for each edge $\left<u,v\right>\in E$ there is some $V_i$ that contains both u and v.
• MEASURE: Cardinality of the clique cover, i.e., the number of subsets $V_i$.

  
  

• Good News: Approximable within $O(f(\vert E\vert))$ if MINIMUM CLIQUE PARTITION is approximable within $f(\vert V\vert)$ [221].
• Bad News: Not approximable within $g(\vert V\vert)^2$ unless MINIMUM CLIQUE PARTITION is approximable within $g(\vert V\vert)$.
• 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 $v_0\in V$ 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 $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ [476].
• Garey and Johnson: GT17