[Rule] GraphPartitioning to SpinGlass

[zazabap]

Source: GraphPartitioning
Target: SpinGlass
Motivation: Maps graph bisection to the Ising model, enabling solvers from statistical physics and quantum computing; the natural formulation in spin variables.
Reference: Barahona, 1982; Lucas, 2014

Reduction Algorithm

Notation:

• Source: undirected graph $G = (V, E)$, $n = |V|$ (even), $m = |E|$
• Target: SpinGlass (Ising model) with $n$ spin variables $s_i \in {-1, +1}$

Variable mapping:

$$s_i = 2x_i - 1 \in {-1, +1}$$

where $x_i \in {0,1}$ is the partition variable ($x_i = 0 \Rightarrow s_i = -1 \Rightarrow i \in A$).

Ising Hamiltonian:

An edge $(u,v)$ is cut iff $s_u \neq s_v$, i.e., $s_u s_v = -1$. The number of cut edges is:

$$\text{cut} = \sum_{(u,v) \in E} \frac{1 - s_u s_v}{2}$$

The balance constraint $|A| = |B| = n/2$ becomes $\sum_i s_i = 0$, enforced as a penalty:

$$H = -\sum_{(u,v) \in E} J_{uv} s_u s_v + P \left(\sum_{i \in V} s_i\right)^2$$

Setting $J_{uv} = -1/2$ for each edge and minimizing $H$ minimizes cut edges under the balance constraint.

Equivalently, the coupling constants are:

• $J_{uv} = -1/2$ for $(u,v) \in E$ (antiferromagnetic — prefers aligned spins = uncut edges)
• $J_{ij} = P$ for all pairs (balance enforcement via a global field)

Solution extraction: $A = {i : s_i = -1}$, $B = {i : s_i = +1}$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_spins	$n$
num_couplings	$\binom{n}{2}$ (pairwise for balance) or $m$ (if balance via external field)

Validation Method

Closed-loop testing: solve GraphPartitioning by brute-force, solve the reduced SpinGlass, and verify both give the same optimal partition.

Example

Source: 6 vertices, 9 edges: $(0,1), (0,2), (1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5)$.

SpinGlass: 6 spins, couplings $J_{uv} = -1/2$ for each edge, penalty $P = 5$ for balance.

Optimal: $s = (-1, -1, -1, +1, +1, +1)$, $\sum s_i = 0$ (balanced).

Cut edges: $(1,3), (2,3), (2,4)$ — each has $s_u s_v = -1$, contributing $+1/2$ to $H$.

$H = -(-1/2)(3 \cdot (-1) + 6 \cdot (+1)) + 5 \cdot 0 = 3/2 + 0$. Minimized among all balanced spin configurations.