Covering by Cliques

Input

Graph $G = (V, E)$, positive integer $K \leq |E|$.

Question

Are there $k \leq K$ subsets $V_1, V_2, \dots, V_k$ of $V$ such that each $V_i$ induces a complete subgraph of $G$ and such that for each edge $\{u, v\} \in E$ there is some $V_i$ that contains both $u$ and $v$?

Classes

• NP-complete

Proofs

NP-complete

Transformation from Partition into Cliques (Kou et al., 1978), (Orlin, 1977).

Reducible from

• Partition into Cliques

References

• Kou, L. T., Stockmeyer, L. J., & Wong, C. K. (1978). Covering edges by cliques with regard to keyword conflicts and intersection graphs. Communications of the ACM, 21(2), 135–139. https://doi.org/10.1145/359340.359346
• Orlin, J. (1977). Contentment in graph theory: Covering graphs with cliques. Indagationes Mathematicae (Proceedings), 80(5), 406–424. https://doi.org/10.1016/1385-7258(77)90055-5