[Rule] GRAPH K-COLORABILITY to PARTITION INTO CLIQUES

[isPANN]

Source: GRAPH K-COLORABILITY

Target: PARTITION INTO CLIQUES
Motivation: The classic complement-graph duality: a K-coloring of G partitions vertices into K independent sets, which are exactly the cliques in the complement graph. This reduction is the canonical proof of NP-completeness for PARTITION INTO CLIQUES (CLIQUE COVER) from Karp (1972).
Reference: Garey & Johnson, Computers and Intractability, A1.1 GT15

GJ Source Entry

[GT15] PARTITION INTO CLIQUES
INSTANCE: Graph G = (V,E), positive integer K ≤ |V|.
QUESTION: Can the vertices of G be partitioned into k ≤ K disjoint sets V_1, V_2, . . . , V_k such that, for 1 ≤ i ≤ k, the subgraph induced by V_i is a complete graph?
Reference: [Karp, 1972] (there called CLIQUE COVER). Transformation from GRAPH K-COLORABILITY.
Comment: Remains NP-complete for edge graphs [Arjomandi, 1977], for graphs containing no complete subgraphs on 4 vertices (see construction for PARTITION INTO TRIANGLES in Chapter 3), and for all fixed K ≥ 3. Solvable in polynomial time for K ≤ 2, for graphs containing no complete subgraphs on 3 vertices (by matching), for circular arc graphs (given their representations as families of arcs) [Gavril, 1974a], for chordal graphs [Gavril, 1972], and for comparability graphs [Golumbic, 1977].

Reduction Algorithm

Summary:
Given a KColoring instance (G, K) where G = (V, E), construct a PartitionIntoCliques instance as follows:

1. Complement graph construction: Build the complement graph G^c = (V, E^c) where E^c = { {u, v} : u, v in V, u != v, {u, v} not in E }. The vertex set is unchanged.
2. Clique bound parameter: Set K' = K (the same number of colors becomes the number of cliques).
3. Output: The PartitionIntoCliques instance (G^c, K').

Correctness:

• A proper K-coloring of G assigns each vertex a color from {1, ..., K} such that no two adjacent vertices share a color.
• The set of vertices assigned the same color forms an independent set in G (no edges between them).
• An independent set in G is exactly a clique in G^c (all pairs of vertices in the set are edges in G^c).
• Therefore, the K color classes form a partition of V into at most K cliques in G^c.
• Conversely, given a partition of V into at most K cliques in G^c, each clique is an independent set in G, so assigning all vertices in the same clique the same color yields a proper K-coloring of G.

Key invariant: A subset S of V is an independent set in G if and only if S is a clique in G^c.

Solution extraction: Given a partition {V_1, ..., V_k} of the vertices of G^c into cliques, assign color i to all vertices in V_i. This yields a valid K-coloring of the original graph G.

Size Overhead

Symbols:

• n = num_vertices of source G
• m = num_edges of source G

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices
num_edges	num_vertices * (num_vertices - 1) / 2 - num_edges
num_cliques	num_colors

Derivation: The complement graph has the same n vertices. The complete graph K_n has n(n-1)/2 edges; the complement has n(n-1)/2 - m edges. The clique bound K is identical to the color bound.

Validation Method

• Closed-loop test: reduce a KColoring instance to PartitionIntoCliques, solve the target with BruteForce, extract clique partition, map back to coloring (each clique = one color class), verify it is a valid K-coloring of the original graph.
• Verify that the complement graph has the correct number of edges: |E^c| = n(n-1)/2 - |E|.
• Check small known cases: C_5 (5-cycle) is 3-colorable; complement of C_5 is C_5 (self-complementary), and C_5 has clique cover number 3.

Example

Source instance (KColoring):
Graph G with 5 vertices {0, 1, 2, 3, 4} and edges forming a 4-cycle plus one chord, K = 3:

• Edges: {0,1}, {1,2}, {2,3}, {3,0}, {0,2}
• (Square with one diagonal)
• A valid 3-coloring: 0->Red, 1->Blue, 2->Green, 3->Blue
• Chromatic number is 3 (triangle {0,1,2} requires 3 colors)

Constructed target instance (PartitionIntoCliques on complement):
Complement graph G^c has 5 vertices and edges NOT in G:

• Total possible edges in K_5: 10
• Edges in G: 5
• Edges in G^c: 10 - 5 = 5
• G^c edges: {0,4}, {1,3}, {1,4}, {2,4}, {3,4}
• K' = 3 (same as color bound)

Solution mapping:

• A partition of G^c into at most 3 cliques: V_1 = {1, 3, 4} (check: {1,3} ✓, {1,4} ✓, {3,4} ✓ -- triangle in G^c), V_2 = {0} (trivial clique), V_3 = {2} (trivial clique)
• Map back to coloring of G: vertices {1,3,4} get color 1, vertex {0} gets color 2, vertex {2} gets color 3
• Verify on G: edge {0,1}: colors 2,1 ✓, edge {1,2}: colors 1,3 ✓, edge {2,3}: colors 3,1 ✓, edge {3,0}: colors 1,2 ✓, edge {0,2}: colors 2,3 ✓
• All edges have distinct colors ✓

References

• [Karp, 1972]: [Karp1972] Richard M. Karp (1972). "Reducibility among combinatorial problems". In: Complexity of Computer Computations. Plenum Press.
• [Arjomandi, 1977]: [Arjomandi1977] E. Arjomandi (1977). "".
• [Gavril, 1974a]: [Gavril1974a] F. Gavril (1974). "Algorithms on circular-arc graphs". Networks 4, pp. 357–369.
• [Gavril, 1972]: [Gavril1972] F. Gavril (1972). "Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph". SIAM Journal on Computing 1, pp. 180–187.
• [Golumbic, 1977]: [Golumbic1977] M. C. Golumbic (1977). "The complexity of comparability graph recognition and coloring". Computing 18, pp. 199–208.

[GiggleLiu]

Implemented in PR #999.