[Rule] VERTEX COVER to CLIQUE

[isPANN]

Source: VERTEX COVER
Target: CLIQUE
Motivation: Establishes the tight equivalence between VERTEX COVER and CLIQUE via complement graphs, showing that a minimum vertex cover in G directly corresponds to a maximum clique in the complement of G.

Reference: Garey & Johnson, Computers and Intractability, Lemma 3.1, p.54

Reduction Algorithm

Lemma 3.1 For any graph G = (V,E) and subset V' ⊆ V, the following statements are equivalent:

(a) V' is a vertex cover for G.
(b) V-V' is an independent set for G.
(c) V-V' is a clique in the complement G^c of G, where G^c = (V,E^c) with E^c = {{u,v}: u,v E V and {u,v} not-E E}.

Thus we see that, in a rather strong sense, these three problems might be regarded simply as "different versions" of one another. Furthermore, the relationships displayed in the lemma make it a trivial matter to transform any one of the problems to either of the others.

For example, to transform VERTEX COVER to CLIQUE, let G = (V,E) and K <= |V| constitute any instance of VC. The corresponding instance of CLIQUE is provided simply by the graph G^c and the integer J = |V|-K.

This implies that the NP-completeness of all three problems will follow as an immediate consequence of proving that any one of them is NP-complete. We choose to prove this for VERTEX COVER.

Summary:
Given a MinimumVertexCover instance (G, k) where G = (V, E) and k is the cover size bound, construct a MaximumClique instance as follows:

1. Complement graph construction: Build G^c = (V, E^c) where E^c contains exactly those pairs {u, v} that are NOT edges in E (but u ≠ v). The vertex set is unchanged.
2. Clique size parameter: Set J = |V| - k. A vertex cover of size ≤ k in G exists if and only if a clique of size ≥ J in G^c exists.
3. Solution extraction: Given a maximum clique C in G^c of size J, the vertex cover in G is V \ C (the complement of C), which has size |V| - J = k.

Key invariant: V' is a vertex cover in G if and only if V \ V' is a clique in G^c (by Lemma 3.1). Therefore MinVC(G) + MaxClique(G^c) = |V|.

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

Derivation: The complement graph has the same vertices (n). Each pair of vertices either has an edge in G or in G^c (not both). The complete graph K_n has n(n-1)/2 edges, so G^c has n(n-1)/2 - m edges.

Validation Method

• Closed-loop test: reduce source MinimumVertexCover instance to MaximumClique, solve target with BruteForce, extract solution (V \ clique), verify it is a valid vertex cover on the original graph
• Check that max clique size J in G^c satisfies J = n - (minimum VC size in G)
• Compare with known results: path graph P_n has VC of size n-1 and G^c = K_n minus a matching, so clique in complement has size 2

Example

Source instance (MinimumVertexCover):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges: {0,1}, {0,2}, {1,2}, {1,3}, {2,4}, {3,4}, {3,5}
• (Two triangles sharing a path, plus an extra vertex)
• Minimum vertex cover has size k = 3: {1, 2, 3} covers all edges (0-1 by 1, 0-2 by 2, 1-2 by both, 1-3 by both, 2-4 by 2, 3-4 by 3, 3-5 by 3)

Constructed target instance (MaximumClique in G^c):
Complement graph G^c has the same 6 vertices and all edges NOT in G:

• Total possible edges in K_6: 6*5/2 = 15
• Edges in G: 7
• Edges in G^c: 15 - 7 = 8
• G^c edges: {0,3}, {0,4}, {0,5}, {1,4}, {1,5}, {2,3}, {2,5}, {4,5}
• Target clique size: J = 6 - 3 = 3

Solution mapping:

• Maximum clique in G^c: {0, 4, 5} — check: {0,4} ✓, {0,5} ✓, {4,5} ✓ — all edges present in G^c
• Extracted vertex cover in G: V \ {0, 4, 5} = {1, 2, 3}
• Verification: edges {0,1} covered by 1 ✓, {0,2} covered by 2 ✓, {1,2} covered by 1,2 ✓, {1,3} covered by 1,3 ✓, {2,4} covered by 2 ✓, {3,4} covered by 3 ✓, {3,5} covered by 3 ✓
• All 7 edges covered, VC size = 3 = k ✓

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MinimumVertexCover to MaximumClique
Non-trivial	✅ Pass	Complement graph construction is a genuine structural transformation
Correctness	✅ Pass	Garey & Johnson (1979), Lemma 3.1 verified in project bibliography
Well-written	⚠️ Warn	Minor issues with overhead table and symbol consistency

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

Pass. There is no existing reduction path from MinimumVertexCover to MaximumClique in the codebase. MaximumClique currently has zero inbound reductions (reduces_from: []), so this rule adds a genuinely new connection to the reduction graph. The motivation is clear: it establishes a classical equivalence from Garey & Johnson.

Non-trivial

Pass. The reduction constructs a complement graph G^c — this is a genuine structural transformation that iterates over all vertex pairs and inverts the edge relation. It also transforms the objective (min VC size k → max clique size n−k) and requires non-trivial solution extraction (set complement). This is not a simple relabeling or type coercion, even though Garey & Johnson call it "trivial" in the complexity-theoretic sense.

Correctness

Pass. The cited reference is Garey & Johnson, Computers and Intractability, Lemma 3.1, p.54. This book is already in the project bibliography (garey1979 in docs/paper/references.bib). Lemma 3.1 establishes the equivalence between vertex cover, independent set, and clique via complement graphs — this is one of the most well-known results in computational complexity. The reduction algorithm correctly implements the lemma: complement the graph, set J = |V| − k, extract VC as V \ clique. The example is fully verified (see below).

The key invariant MinVC(G) + MaxClique(G^c) = |V| is correct and follows directly from Lemma 3.1.

Well-written

Warn. The issue is generally well-structured and complete, but has minor issues:

1. Overhead table lists num_edges as a target metric, but MaximumClique only reports num_vertices in its size_fields. The num_edges() getter does exist on MaximumClique, so the overhead macro would compile, but the implementation should verify that num_edges is appropriate as an overhead field. Consider whether num_vertices alone suffices — the complement graph has the same number of vertices, and the edge count is fully determined by the source.

2. The overhead expression num_vertices * (num_vertices - 1) / 2 - num_edges uses integer division — the overhead expression parser supports / but the semantics should be verified for even/odd cases. Since n(n−1) is always even, this is fine mathematically, but the expression parser may evaluate this as float division. Worth checking during implementation.

3. All template sections are present and substantive — Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, and Example are all filled in with real content.

4. The example is correct and well-worked:

   • Source: 6 vertices, 7 edges, minimum VC = {1, 2, 3} of size 3 — verified (no VC of size 2 exists)
   • Complement: 8 edges listed correctly (all 8 non-edges of G)
   • Target clique {0, 4, 5} of size 3 — verified all 3 edges present in G^c
   • Solution extraction V \ {0, 4, 5} = {1, 2, 3} — verified covers all 7 edges

5. Symbol definitions are consistent — n, m, G, V, E, G^c, E^c, k, J all defined and used consistently.

Recommendations

• Consider dropping num_edges from the overhead table and using only num_vertices (which is sufficient since MaximumClique's registered size field is num_vertices). The edge count of the complement is derivable from the source dimensions.
• The validation method is solid — closed-loop test with BruteForce is the standard pattern in this codebase.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MinimumVertexCover to MaximumClique in the reduction graph
Non-trivial	✅ Pass	Complement graph construction creates new edge structure
Correctness	✅ Pass	Garey & Johnson (1979) Lemma 3.1 confirmed in project bibliography
Well-written	✅ Pass	All sections present and substantive; algorithm is implementable

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

No reduction path currently exists from MinimumVertexCover to MaximumClique (pred path returns no result). The only existing reductions from MinimumVertexCover are to MaximumIndependentSet and MinimumSetCovering. This rule adds a novel direct edge in the reduction graph.

Note: the existing codebase already has MIS ↔ MinVC reductions, but no MIS → MaxClique or MinVC → MaxClique. This rule fills a gap in the graph.

Non-trivial

The reduction constructs the complement graph G^c, which involves building an entirely new edge set. While Garey & Johnson themselves describe it as a "trivial matter," the construction does involve genuine structural transformation (computing edge complements and adjusting the optimization parameter). It is not a mere variable relabeling, subtype coercion, or identity mapping.

Correctness

• Reference: Garey & Johnson, Computers and Intractability (1979), Lemma 3.1, p.54. This book is already in the project bibliography (garey1979 in docs/paper/references.bib). The claim matches the known result exactly.
• Cross-check: The project's references.md confirms: "MIS ↔ Clique (IS in G = Clique in complement(G))" and "Clique → Vertex Cover (complement graph: VC = n - Clique)."
• Overhead verification: The complement graph formula num_vertices * (num_vertices - 1) / 2 - num_edges is correct — K_n has n(n-1)/2 edges, and G^c = K_n \ G.
• Example verified: The 6-vertex example is correct. The complement graph edges are accurate (8 edges), the clique {0,4,5} is valid in G^c, and {1,2,3} is indeed a minimum vertex cover of size 3.

Well-written

All required sections are present and substantive:

• ✅ Source/Target: Identified (though uses informal names "VERTEX COVER" / "CLIQUE" rather than codebase names MinimumVertexCover / MaximumClique)
• ✅ Motivation: Explains the equivalence relationship
• ✅ Reference: Garey & Johnson Lemma 3.1
• ✅ Reduction Algorithm: Complete 3-step procedure with solution extraction
• ✅ Size Overhead: Table with derivation. Note: num_edges is listed as a target metric; while MaximumClique's size_fields only reports num_vertices, the num_edges() getter method does exist on the type, so the overhead expression is valid for the #[reduction] macro
• ✅ Validation Method: Closed-loop test described
• ✅ Example: Non-trivial 6-vertex instance, fully worked with step-by-step verification

Recommendations

• Consider using the codebase problem names (MinimumVertexCover, MaximumClique) in the Source/Target fields for consistency with the project naming conventions.
• Since MIS ↔ MinVC and MIS → MaxClique (via complement) are closely related, an alternative implementation path would be MIS → MaxClique directly (IS in G = Clique in G^c). The proposed MinVC → MaxClique is equivalent but composes two steps conceptually (VC complement = IS, IS in G = Clique in G^c). Either approach is valid.

[isPANN]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	❌ Fail	Redundant — existing path MinVC → MIS → MaxClique has identical overhead
Non-trivial	✅ Pass	Complement graph construction is genuine structural transformation
Correctness	✅ Pass	GJ Lemma 3.1 verified; example brute-force confirmed
Well-written	✅ Pass	All sections present, algorithm clear, example fully worked

Overall: 3 passed, 1 failed, 0 warnings

---

Usefulness

Fail. An existing 2-step path already reaches MaximumClique from MinimumVertexCover:

1. MinimumVertexCover {SimpleGraph, i32} → MaximumIndependentSet {SimpleGraph, i32} (set complement, same graph)
2. MaximumIndependentSet {SimpleGraph, i32} → MaximumClique {SimpleGraph, i32} (complement graph)

Overhead comparison:

Field	Proposed direct rule	Existing 2-step path
num_vertices	num_vertices	num_vertices
num_edges	num_vertices * (num_vertices - 1) / 2 - num_edges	num_vertices * (num_vertices - 1) / 2 - num_edges

The overheads are identical. The proposed direct rule composes the same two operations (VC↔IS set complement + IS↔Clique graph complement) into a single step, but provides no overhead improvement. The existing composite path dominates.

Non-trivial

Pass. The reduction constructs a complement graph G^c — this iterates over all vertex pairs and inverts the edge relation, producing a genuinely different graph structure. The objective is also transformed (min VC size k → max clique size n−k). This is not a simple relabeling or type coercion.

Correctness

Pass.

• Reference: Garey & Johnson (1979), Computers and Intractability, Lemma 3.1, p.54 — already in bibliography as garey1979. The equivalence between vertex cover, independent set, and clique via complement graphs is one of the most well-known results in complexity theory.
• Overhead formula: num_vertices * (num_vertices - 1) / 2 - num_edges is correct — K_n has n(n-1)/2 edges, G^c = K_n \ G.
• Example verified (brute-force Python script):
  • Source: {1, 2, 3} is a valid minimum VC of size 3 (no VC of size 2 exists; one other min VC: {0, 2, 3})
  • Complement: all 8 listed edges correct
  • Target: {0, 4, 5} is a valid maximum clique of size 3 (one other max clique: {1, 4, 5})
  • Round-trip: V \ {0, 4, 5} = {1, 2, 3} ✓, 6 - 3 = 3 ✓
  • 15 suboptimal VCs, 8 suboptimal cliques — ample non-trivial solutions

Well-written

Pass. All required sections present and substantive. Algorithm is a clear 3-step procedure with solution extraction. Overhead table uses correct target getter names (num_vertices, num_edges — both in MaximumClique's size_fields). Source variables match source's size_fields. Example is fully worked with edge-by-edge verification.

Recommendations

• This reduction is redundant given the existing MinVC ↔ MIS ↔ MaxClique path. Consider closing or deprioritizing this issue.
• If the goal is educational documentation (showing Lemma 3.1 directly), it could be kept as a paper-only entry without codebase implementation.