Partition into Cliques

Input

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

Question

Can the vertices of $G$ be partitioned into $k \leq K$ disjoint sets $V_1, V_2, \dots, V_k$ such that for $1 \leq i \leq k$, the subgraph induced by $V_i$ is a complete graph?

Classes

• NP-complete

Comments

Remains NP-complete for edge graphs, for graphs containing no complete subgraphs on 4 vertices, and for all fixed $K \geq 3$. Solvable in polynomial time for $K \leq 2$, for graphs containing no complete subgraphs on 3 vertices (by matching), for circular arc graphs (given their representations as families of arcs) (Gavril, 1974), for chordal graphs (Gavril, 1972), and for comparability graphs (Golumbic, 1977).

Proofs

NP-complete

Transformation from Graph K-Colorability (Karp, 1972).

Reducible from

• Graph K-Colorability

Reducible to

• Covering by Cliques
• Covering by Complete Bipartite Subgraphs

References

• Gavril, F. (1974). Algorithms on circular-arc graphs. Networks, 4(4), 357–369. https://doi.org/10.1002/net.3230040407
• Gavril, F. (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing, 1(2), 180–187. https://doi.org/10.1137/0201013
• Golumbic, M. C. (1977). The complexity of comparability graph recognition and coloring. Computing, 18(3), 199–208. https://doi.org/10.1007/bf02253207
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9