[Rule] PARTITION INTO CLIQUES to MinimumCoveringByCliques

[isPANN]

Source: PARTITION INTO CLIQUES (PartitionIntoCliques)
Target: MINIMUM COVERING BY CLIQUES (MinimumCoveringByCliques)

Motivation: The current issue body uses the identity map G' = G, K' = K. That is false: a partition into K cliques does imply an edge-clique cover with K cliques, but the converse fails. The correct classical reduction is non-trivial. The construction below is a direct inlining of Orlin's original reduction chain
P0 -> P1 -> P2 -> P3
from vertex-clique-cover to edge-clique-cover.

Reference: Garey & Johnson, Computers and Intractability, GT17; James Orlin, "Contentment in graph theory: Covering graphs with cliques" (1977), Theorem 8.1; Kou, Stockmeyer, and Wong (1978).

GJ Source Entry

[GT17] COVERING BY CLIQUES
INSTANCE: Graph G = (V, E), positive integer K <= |V|.
QUESTION: Are there k <= K subsets V_1, ..., V_k such that each V_i induces a clique of G and every edge of G has both endpoints in at least one V_i?
Reference: [Kou, Stockmeyer, and Wong, 1978], [Orlin, 1977]. Transformation from PARTITION INTO CLIQUES.

Preliminaries

A family of at most K cliques that covers all vertices can always be turned into a partition into at most K cliques: assign each vertex to one covering clique arbitrarily, and delete it from the others. Subcliques remain cliques. So the source problem may be read as either vertex-clique-cover or partition-into-cliques.

Reduction Algorithm

Input:

• a graph G = (V, E)
• an integer K
• an indexing V = {v_1, ..., v_n}

Let
A = { (i,j) | i != j and {v_i, v_j} in E }.
So |A| = 2|E|.

Create the following vertices:

• original left vertices x_1, ..., x_n
• original right vertices y_1, ..., y_n
• gadget left vertices a_(i,j) for every (i,j) in A
• gadget right vertices b_(i,j) for every (i,j) in A
• two special vertices z_L, z_R

Let

• L = {x_i : 1 <= i <= n} union {a_(i,j) : (i,j) in A}
• R = {y_i : 1 <= i <= n} union {b_(i,j) : (i,j) in A}

Construct the target graph H as follows.

1. Make L a clique.
2. Make R a clique.
3. Add z_L adjacent to every vertex of L.
4. Add z_R adjacent to every vertex of R.
5. For every i, add the matching edge x_i y_i.
6. For every (i,j) in A, add the four cross edges
   • x_i y_j
   • x_i b_(i,j)
   • a_(i,j) y_j
   • a_(i,j) b_(i,j)

Set
K' = K + |A| + 2 = K + 2|E| + 2.

Output the MinimumCoveringByCliques instance (H, K').

Forward Witness Map

Suppose the source graph has a partition into at most K cliques
C_1, ..., C_K.

For each source clique C_t, define the target clique
D_t = { x_i, y_i | v_i in C_t }.

For each (i,j) in A, define the gadget clique
Q_(i,j) = { x_i, a_(i,j), b_(i,j), y_j }.

Also define the two side cliques

• L* = L union {z_L}
• R* = R union {z_R}

Claim: the family
{D_1, ..., D_K} union {Q_(i,j) : (i,j) in A} union {L*, R*}
is an edge-clique cover of H.

Reason:

• each D_t is a clique because if v_i, v_j in C_t, then either i=j or {v_i,v_j} in E, hence both x_i y_j and x_j y_i are present;
• each Q_(i,j) is a clique by construction;
• L* covers all left-left edges and all edges incident to z_L;
• R* covers all right-right edges and all edges incident to z_R;
• the matching edges x_i y_i are covered by the appropriate D_t;
• every off-diagonal cross edge x_i y_j with (i,j) in A is covered by Q_(i,j) and also by D_t whenever v_i, v_j lie in the same source clique.

Thus H has an edge-clique cover of size
K + |A| + 2 = K'.

Extraction Pass

Now suppose H has an edge-clique cover F with |F| <= K'.

Step 1: Normalize the forced gadget cliques

For each (i,j) in A, the edge a_(i,j) b_(i,j) lies in the unique maximal clique
Q_(i,j) = { x_i, a_(i,j), b_(i,j), y_j }.

So without increasing the number of cliques, normalize F so that for every (i,j) in A, one copy of Q_(i,j) is present.

Keep one copy of each Q_(i,j) and delete duplicates.

Step 2: Normalize the two side cliques

Any clique containing z_L can contain only vertices of L, because z_L has no neighbors in R union {z_R}.
Hence replace all cliques containing z_L by the single clique L* = L union {z_L}.

Similarly replace all cliques containing z_R by the single clique R* = R union {z_R}.

After this normalization, keep exactly one copy of L* and one copy of R*.

Step 3: Remove all edges already handled

The cliques from Step 1 cover:

• every edge a_(i,j) b_(i,j)
• every edge x_i b_(i,j)
• every edge a_(i,j) y_j
• every off-diagonal source edge x_i y_j for (i,j) in A

The cliques from Step 2 cover:

• every left-left edge
• every right-right edge
• every edge incident to z_L
• every edge incident to z_R

Therefore the only edges still not guaranteed covered are the matching edges
x_i y_i, 1 <= i <= n.

Step 4: Shrink the remaining cliques to matched pairs

Take every clique of F other than the Q_(i,j), L*, and R*.
Delete from it:

• every gadget vertex a_(i,j) and b_(i,j),
• every x_i for which y_i is not also present,
• every y_i for which x_i is not also present.

After this shrinking, every remaining nonempty clique has the form
{ x_i, y_i : i in S }
for some index set S.

Step 5: Read off source cliques

For every remaining nonempty clique C, define
S(C) = { v_i | x_i in C and y_i in C }.

Then S(C) is a clique in the source graph:
if v_i, v_j in S(C) with i != j, then x_i and y_j lie in the same clique C, so x_i y_j must be an edge of H; by construction this implies {v_i, v_j} in E.

Because none of the cliques Q_(i,j), L*, R* covers any matching edge x_i y_i, every matching edge must be covered by one of these remaining cliques.
Hence every source vertex v_i belongs to at least one set S(C).

So the sets S(C) form a vertex-clique-cover of the source graph using at most K cliques.

Finally, convert this cover into a partition by assigning each vertex to one covering clique arbitrarily.

Correctness

G has a partition into at most K cliques
iff
H has an edge-clique cover of size at most
K + 2|E(G)| + 2.

Size Overhead

Let n = |V(G)| and m = |E(G)|.
Let p = n + 2m.

Then:

• |V(H)| = 2p + 2 = 2n + 4m + 2
• |E(H)| = p^2 + 2n + 10m
• K' = K + 2m + 2

So the reduction is polynomial.

Example

Take the source graph

• V = {1,2,3}
• E = {{1,2}}
• K = 2

A source partition is

• {1,2}
• {3}

Here
A = {(1,2), (2,1)}.

The target graph has

• left side L = {x_1, x_2, x_3, a_(1,2), a_(2,1)}
• right side R = {y_1, y_2, y_3, b_(1,2), b_(2,1)}
• special vertices z_L, z_R
• bound K' = 2 + 2 + 2 = 6

One valid target cover is:

• D_1 = {x_1, x_2, y_1, y_2}
• D_2 = {x_3, y_3}
• Q_(1,2) = {x_1, a_(1,2), b_(1,2), y_2}
• Q_(2,1) = {x_2, a_(2,1), b_(2,1), y_1}
• L*
• R*

Extraction recovers the source cliques {1,2} and {3}.

Implementation Notes

1. Do not use the identity map G' = G, K' = K. It is incorrect.
2. The construction above is an inline composition of Orlin's original P0 -> P1 -> P2 -> P3 proof.
3. If the codebase prefers to store intermediate instances, keep the same objects but expose the matching edges x_i y_i as the annotated edge set in the first intermediate problem.

[GiggleLiu]

fix-issue changelog:

• Rewrote issue body with clean identity-map construction (same graph, same bound)
• Clarified forward direction: partition is trivially a valid covering (disjointness implies covering)
• Clarified backward direction gap: covering allows vertex overlap, may be strictly cheaper than partition
• Added primary example: 5 vertices with K_3 + K_2 partition (K=2)
• Added gap-illustrating example showing covering can be cheaper than partitioning
• Noted MinimumCoveringByCliques -> ILP companion rule needed (no current ILP path)
• Flagged Codex verification for backward extract_solution
• Removed AI-unverified warnings