[Rule] COVERING BY CLIQUES to MinimumIntersectionGraphBasis

[isPANN]

Source: COVERING BY CLIQUES
Target: INTERSECTION GRAPH BASIS
Motivation: This reduction establishes NP-completeness of the Intersection Graph Basis problem (GT59) via transformation from Covering by Cliques (GT17). The key mathematical insight is that the edge clique cover number of a graph equals its intersection number, making the two problems essentially equivalent reformulations.
Reference: Garey & Johnson, Computers and Intractability, A1.5 GT59

Reduction Algorithm

INSTANCE: Graph G = (V,E), positive integer K ≤ |E|.
QUESTION: Is G the intersection graph for a family of sets whose union has cardinality K or less, i.e., is there a K-element set S and for each v ∈ V a subset S[v] ⊆ S such that {u,v} ∈ E if and only if S[u] and S[v] are not disjoint?

Reference: [Kou, Stockmeyer, and Wong, 1978]. Transformation from COVERING BY CLIQUES.

Given an instance (G = (V, E), K) of Covering by Cliques, construct an instance (G, K) of Intersection Graph Basis with the same graph and the same bound K.

The reduction is the identity mapping. The equivalence follows from the theorem (Erdos, Goodman, and Posa, 1966; Kou, Stockmeyer, and Wong, 1978) that the minimum number of cliques needed to cover all edges of G equals the intersection number of G.

Correctness: Given a clique edge cover {C_1, ..., C_k} with k ≤ K, define universe S = {1, ..., k} and for each vertex v ∈ V, let S[v] = {i : v ∈ C_i}. Then {u,v} ∈ E iff there exists a clique C_i containing both u and v iff i ∈ S[u] ∩ S[v] iff S[u] ∩ S[v] ≠ ∅. Conversely, given an intersection representation with universe S of size k ≤ K, for each element s ∈ S define C_s = {v : s ∈ S[v]}. Each C_s is a clique (any two vertices sharing element s are adjacent), and every edge is covered (adjacent vertices share at least one element).

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vertices	num_vertices (identity)
num_edges	num_edges (identity)
universe_size	num_cliques (identity)

The reduction is the identity transformation: the graph is unchanged and K maps directly to K.

Validation Method

1. Construct a small graph (e.g., a triangle with a pendant edge: 4 vertices, 4 edges).
2. Run the reduction (identity): same graph, same K.
3. Verify that a YES instance of Covering by Cliques with k cliques yields a YES instance of Intersection Graph Basis with universe size k, and vice versa, by explicitly constructing the set family from the clique cover.

Example

Source instance (Covering by Cliques):
Graph: triangle {0,1,2} plus edge {2,3}. Edges: {0,1}, {0,2}, {1,2}, {2,3}. K = 2.

Clique cover: C_1 = {0,1,2} (covers {0,1}, {0,2}, {1,2}), C_2 = {2,3} (covers {2,3}). Total: 2 cliques.

Target instance (Intersection Graph Basis):
Same graph, K = 2. Universe S = {1, 2}.

• S[0] = {1} (vertex 0 is in C_1)
• S[1] = {1} (vertex 1 is in C_1)
• S[2] = {1, 2} (vertex 2 is in C_1 and C_2)
• S[3] = {2} (vertex 3 is in C_2)

Check: S[0] ∩ S[1] = {1} ≠ ∅ (edge); S[0] ∩ S[2] = {1} ≠ ∅ (edge); S[1] ∩ S[2] = {1} ≠ ∅ (edge); S[2] ∩ S[3] = {2} ≠ ∅ (edge); S[0] ∩ S[3] = ∅ (non-edge); S[1] ∩ S[3] = ∅ (non-edge). Valid intersection representation with universe size 2.

References

• [Kou, Stockmeyer, and Wong, 1978]: [Kou1978] Lawrence T. Kou and Lawrence J. Stockmeyer and Chak K. Wong (1978). "Covering edges by cliques with regard to keyword conflicts and intersection graphs". Communications of the ACM 21, pp. 135-138.
• [Erdos, Goodman, and Posa, 1966]: Paul Erdos, A. W. Goodman, and Louis Posa (1966). "The representation of a graph by set intersections". Canadian Journal of Mathematics 18, pp. 106-112.