[Rule] MaximumIndependentSet to MaximumClique

[zazabap]

Source: MaximumIndependentSet
Target: MaximumClique
Motivation: An independent set in $G$ corresponds to a clique in the complement graph; this is the reverse of Karp's classical complement graph reduction.
Reference: Karp, R. M. (1972). Reducibility among combinatorial problems.

Reduction Algorithm

Notation:

• Source: MaximumIndependentSet instance on graph $G = (V, E)$ with vertex weights $w$
• $n = |V|$, $m = |E|$
• Complement graph: $\bar{G} = (V, \bar{E})$ where $\bar{E} = {(u,v) : u \neq v,; (u,v) \notin E}$

Variable mapping:

• Vertices are preserved: vertex $i$ in $G$ maps to vertex $i$ in $\bar{G}$
• Weights are preserved: $w_i$ in the source maps to $w_i$ in the target
• Configuration is identity: $\text{config}[i]$ in source equals $\text{config}[i]$ in target

Constraint/objective transformation:

• A set $S$ is an independent set in $G$ iff no pair in $S$ is adjacent in $G$ iff all pairs in $S$ are adjacent in $\bar{G}$ iff $S$ is a clique in $\bar{G}$
• Objective (maximize total weight of selected vertices) is identical in both problems

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vertices	$n$
num_edges	$n(n-1)/2 - m$

Validation Method

Closed-loop test: construct a MaximumIndependentSet instance, reduce to MaximumClique, solve both with BruteForce, verify optimal values match and extracted solution is a valid independent set in the original graph.

Example

Source: MaximumIndependentSet on triangle $K_3$ with 3 vertices, edges ${(0,1), (1,2), (0,2)}$, unit weights.

• $n=3$, $m=3$
• Complement $\bar{G}$ has edges $\emptyset$ (empty graph), so $|\bar{E}| = 3 \cdot 2/2 - 3 = 0$

Reduction: Build MaximumClique on $\bar{G}$ (the empty graph on 3 vertices) with same weights.

Target: MaximumClique on $\bar{G} = ({0,1,2},; \emptyset)$.

Solution: In $\bar{G}$ (empty graph), every single vertex is a trivial max clique of size 1. Back in $G$, any single vertex is an independent set of size 1. This is optimal ($K_3$ has no independent set of size $> 1$).

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing reduction path from MaximumIndependentSet to MaximumClique
Non-trivial	⚠️ Warn	Complement graph construction is structural but borderline — identity variable mapping with no gadgets or auxiliary variables
Correctness	✅ Pass	Karp (1972) is verified in project bibliography and references.md confirms MIS ↔ Clique via complement graph
Well-written	✅ Pass	All sections present, algorithm is implementable, notation is consistent

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

pred path MaximumIndependentSet MaximumClique returns "No reduction path." This is a novel direct reduction in the graph. The reduction is one of Karp's classical 21 reductions and a fundamental building block in complexity theory. It enables reaching MaximumClique from any problem that already reduces to MIS.

Non-trivial

The reduction constructs the complement graph G-bar = (V, E-bar) where E-bar = {(u,v) : u ≠ v, (u,v) ∉ E}. The edge set is completely recomputed — this is genuine structural transformation of the graph. However, the variable mapping is identity (config[i] in source = config[i] in target), and there are no gadgets, penalty terms, or auxiliary variables. The objective function is preserved identically.

This is a classical and well-established reduction, so it passes, but it is worth noting that among all reductions in the codebase, this is one of the simplest structurally — the "transformation" is entirely in rewriting the adjacency structure via complement.

Correctness

Reference: Karp, R. M. (1972). "Reducibility among Combinatorial Problems."

• Already present in docs/paper/references.bib as karp1972 (pages 85–103, Complexity of Computer Computations, Plenum Press).
• The DOI 10.1007/978-1-4684-2001-2_9 is the correct Springer chapter DOI for this work.
• The references.md knowledge base confirms: "MIS ↔ Clique: IS in G = Clique in complement(G)" (from Garey & Johnson, Chapter 3).
• The mathematical claim is correct: S is an independent set in G if and only if S is a clique in the complement graph G-bar. This is a textbook result (Garey & Johnson 1979, p. 54).

Overhead verification:

• num_vertices = n: correct — vertices are preserved.
• num_edges = n(n-1)/2 - m: correct — complement graph has exactly C(n,2) - m edges.
• Both num_vertices and num_edges are valid getter methods on MaximumClique (verified in source code).

No better algorithms or alternative constructions found — this is the canonical and optimal reduction with linear vertex overhead and polynomial edge overhead.

Well-written

Information Completeness: All 8 required sections are present and substantive:

• ✅ Source: MaximumIndependentSet
• ✅ Target: MaximumClique
• ✅ Motivation: clearly explains the complement graph relationship and connection to Karp's reductions
• ✅ Reference: Karp 1972 with DOI
• ✅ Reduction Algorithm: complete step-by-step procedure with notation, variable mapping, and constraint/objective transformation
• ✅ Size Overhead: table with correct code metric names (num_vertices, num_edges) and formulas
• ✅ Validation Method: closed-loop test description
• ✅ Example: worked K_3 instance

Algorithm Completeness: The algorithm is detailed enough to implement: notation defines all symbols (G, V, E, n, m, G-bar, E-bar), variable mapping is explicit, and the correctness argument (S is IS in G iff S is clique in G-bar) is clearly stated.

Symbol Consistency: All symbols are defined before use. n = |V|, m = |E| are defined in Notation and used consistently in the overhead table. Code metric names match actual getter methods on the target type.

Example Quality: The K_3 example is minimal but valid — it demonstrates that the complement of a complete graph is the empty graph, and correctly traces the solution (single vertex) back to the source. It could be slightly more illustrative with a non-trivial graph (e.g., a path graph P_4 where the complement is more interesting), but it is sufficient.

Recommendations

• Consider using a slightly richer example (e.g., path P_4 or cycle C_5) where both the source IS and target clique have size > 1, to better demonstrate the reduction's utility.
• The overhead expression for num_edges will need to be written as num_vertices * (num_vertices - 1) / 2 - num_edges in the #[reduction(overhead = {...})] macro, since it uses source getter method names.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MaximumIndependentSet to MaximumClique in the reduction graph
Non-trivial	✅ Pass	Complement graph construction is a genuine structural transformation (Karp's classic reduction)
Correctness	✅ Pass	Karp (1972) verified in project bibliography and references.md; MIS ↔ Clique via complement is well-established
Well-written	⚠️ Warn	Minor issues noted below

Overall: 3 passed, 0 failed, 1 warning

---

Usefulness

No reduction path currently exists from MaximumIndependentSet to MaximumClique (pred path returns no result). This is a novel addition to the reduction graph. The reverse direction (MaximumClique → MIS) also does not exist, so this is the first link between these two problems. As one of Karp's 21 classical NP-complete reductions, this is a fundamental edge in the reduction graph.

Non-trivial

The reduction constructs the complement graph, which involves computing a new edge set: all non-edges become edges and vice versa. While the vertex set and variable mapping are identity, the structural transformation of the graph is non-trivial — the complement graph can have a completely different topology (e.g., a sparse graph becomes dense). This is a well-known and foundational reduction, not a simple relabeling or subtype coercion.

Correctness

• Karp, R. M. (1972). "Reducibility among Combinatorial Problems." — Present in the project bibliography (docs/paper/references.bib as karp1972). The MIS ↔ Clique complement reduction is confirmed in:

  • references.md: "MIS ↔ Clique | IS in G = Clique in complement(G)"
  • Garey & Johnson (1979), Table of classic reductions
  • Wikipedia: Karp's 21 NP-complete problems

• The mathematical claim is correct: a set S is independent in G iff S is a clique in the complement graph, since independent means no pair is adjacent in G, which means every pair is adjacent in the complement.

• The overhead formulas are correct: num_vertices = n (vertices preserved), num_edges = n(n-1)/2 - m (complement edges).

Well-written

Mostly complete and clear. Minor observations:

• Overhead table num_edges field: pred show MaximumClique --json reports size_fields: ["num_vertices"] only, suggesting MaximumClique may not register num_edges as a tracked size field. However, the num_edges() getter method does exist on MaximumClique, so it can be used in #[reduction(overhead = {...})] expressions. This is a minor inconsistency to be aware of during implementation.

• Example quality: The K_3 example (complete graph on 3 vertices) works correctly but is minimal — the complement is the empty graph, which is a degenerate case. A slightly richer example (e.g., a path graph P_4 with 4 vertices and 3 edges, whose complement has 4 vertices and 3 edges, showing a non-trivial clique) would better illustrate the reduction. However, the current example is mathematically correct and fully worked.

• All template sections (Source, Target, Motivation, Reference, Reduction Algorithm, Size Overhead, Validation Method, Example) are present and substantive.

• Symbols are consistent across sections: G, V, E, n, m are defined in the Notation block and used consistently throughout.

Recommendations

• Consider adding a second, slightly larger example (e.g., P_4 or C_5) alongside the K_3 example to demonstrate a non-degenerate case where the complement graph has non-trivial cliques.