[Rule] MaximumClique to MaximumIndependentSet

[zazabap]

Source: MaximumClique
Target: MaximumIndependentSet
Motivation: A clique in $G$ corresponds to an independent set in the complement graph; this is one of Karp's classical reductions connecting two fundamental NP-hard graph problems.
Reference: Karp, R. M. (1972). Reducibility among combinatorial problems.

Reduction Algorithm

Notation:

• Source: MaximumClique 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 a clique in $G$ iff all pairs in $S$ are adjacent in $G$ iff no pair in $S$ is adjacent in $\bar{G}$ iff $S$ is an independent set 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 MaximumClique instance, reduce to MaximumIndependentSet, solve both with BruteForce, verify optimal values match and extracted solution is a valid clique in the original graph.

Example

Source: MaximumClique on path graph $P_4$ with 4 vertices, edges ${(0,1), (1,2), (2,3)}$, unit weights.

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

Reduction: Build MaximumIndependentSet on $\bar{G}$ with same weights.

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

Solution: In $\bar{G}$, vertices ${1,2}$ are non-adjacent → independent set of size 2. Back in $G$, vertices ${1,2}$ are adjacent → clique of size 2. This is optimal ($P_4$ has no triangle).

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing path from MaximumClique to MaximumIndependentSet
Non-trivial	✅ Pass	Complement graph construction builds a new edge set
Correctness	✅ Pass	Karp (1972) verified in project bibliography; reduction confirmed by Garey & Johnson
Well-written	✅ Pass	All sections complete, notation consistent, example fully worked

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

pred path MaximumClique MaximumIndependentSet returns no existing path. This reduction adds a novel direct edge to the reduction graph. Currently MaximumClique only reduces to ILP; adding a path to MaximumIndependentSet connects it to the broader MIS subgraph (MinimumVertexCover, MaximumSetPacking, QUBO, etc.), which is a significant improvement in graph connectivity.

Non-trivial

The reduction constructs the complement graph, replacing the edge set E with its complement E_bar = {(u,v) : u != v, (u,v) not in E}. While vertex labels and weights are preserved (identity variable mapping), the edge set undergoes genuine structural transformation -- every non-edge becomes an edge and vice versa. This is a classical and well-established construction, not a mere type cast or relabeling.

Correctness

The cited reference is Karp, R. M. (1972), "Reducibility among Combinatorial Problems," which is already present in the project bibliography (docs/paper/references.bib, entry karp1972). The clique-to-independent-set complement reduction is explicitly listed in the project's references.md knowledge base under "Classic Reductions from Garey & Johnson" as "MIS <-> Clique: IS in G = Clique in complement(G)." The mathematical claim that a set S is a clique in G iff S is an independent set in the complement of G is a standard textbook result.

The overhead formulas are correct:

• num_vertices = n (vertices preserved)
• num_edges = n(n-1)/2 - m (complement edge count)

These match the target problem's size_fields: ["num_edges", "num_vertices"].

Well-written

All required template sections are present and substantive:

Section	Status
Source	MaximumClique — valid problem name
Target	MaximumIndependentSet — valid problem name
Motivation	Explains the classical complement relationship and Karp's reduction
Reference	Karp (1972) with DOI link
Reduction Algorithm	Complete: notation defined, variable mapping explicit, constraint transformation proved
Size Overhead	Table with correct code metric names and formulas
Validation Method	Closed-loop test pattern described
Example	P4 graph (4 vertices), fully worked with verification

Notation is consistent: n = |V| and m = |E| are defined in the Notation subsection and used consistently in the overhead table. The example arithmetic checks out: P4 has 3 edges, complement has 6 - 3 = 3 edges {(0,2),(0,3),(1,3)}, and the optimal clique {1,2} correctly maps to an independent set of size 2 in the complement.

Recommendations

• The overhead expression for num_edges in code will be num_vertices * (num_vertices - 1) / 2 - num_edges — the implementer should note that num_edges on the source side refers to MaximumClique::num_vertices() (the only size field), so the complement edge count may need to be computed from the graph directly rather than from a getter. Verify that MaximumClique exposes a num_edges() getter or that the overhead expression uses available getters only.

[zazabap]

Issue Quality Check — Rule

Check	Result	Details
Usefulness	✅ Pass	No existing reduction path from MaximumClique to MaximumIndependentSet
Non-trivial	✅ Pass	Complement graph construction creates new edge structure
Correctness	✅ Pass	Karp (1972) verified in project bibliography; reduction is classical
Well-written	✅ Pass	All sections complete, symbols consistent, example fully worked

Overall: 4 passed, 0 failed, 0 warnings

---

Usefulness

No existing reduction path exists from MaximumClique to MaximumIndependentSet (pred path confirms). MaximumClique currently only reduces to ILP. This reduction adds a direct, low-overhead connection between two fundamental graph problems — strictly beneficial for the reduction graph.

Non-trivial

The reduction constructs the complement graph, which involves building a new edge set (all non-edges become edges and vice versa). This is a genuine structural transformation of the graph, not a simple variable substitution or subtype coercion. It is one of Karp's classical reductions and is listed in the project's references.md as a key reduction.

Correctness

• Karp (1972) — "Reducibility among Combinatorial Problems" — already in the project bibliography as karp1972. The clique-to-independent-set complement reduction is explicitly described in this paper and is one of the most well-known reductions in complexity theory.
• The DOI 10.1007/978-1-4684-2001-2_9 is valid.
• The mathematical claim is correct: a set S is a clique in G iff S is an independent set in the complement graph. This is confirmed by Garey & Johnson (1979) and the project's own references.md.
• The overhead formula num_edges = n(n-1)/2 - m correctly counts complement edges. The target size fields num_vertices and num_edges match the MIS problem's getter methods.

Well-written

All required sections are present and substantive:

• Source/Target: Valid problem names matching the codebase.
• Motivation: Clearly explains the classical connection via complement graphs.
• Reference: Proper citation with DOI.
• Reduction Algorithm: Complete step-by-step procedure with notation defined, variable mapping explicit, and constraint transformation clearly stated.
• Size Overhead: Table uses correct target metric code names (num_vertices, num_edges) with correct formulas. Note: the source problem has both num_vertices() and num_edges() getter methods available for overhead expressions.
• Validation Method: Closed-loop test described.
• Example: Fully worked on P4 (4 vertices). The complement edge count (3) and the optimal solution ({1,2}, clique of size 2) are verified correct.

Recommendations

• None. This is a clean, well-documented classical reduction.