[Rule] GraphPartitioning to MaxCut

[zazabap]

Source: GraphPartitioning
Target: MaxCut
Motivation: Reveals the duality between minimizing and maximizing cut edges; enables using MaxCut solvers for bisection via a complementary objective.
Reference: Garey, Johnson & Stockmeyer, 1976

Reduction Algorithm

Notation:

• Source: undirected graph $G = (V, E)$, $n = |V|$ (even), $m = |E|$
• Target: MaxCut on a modified weighted graph $G' = (V, E')$

Key idea: Add penalty-weighted edges on the complete graph to enforce balance, then maximize the total cut.

Construction:

1. $V' = V$ (same vertices).

2. For each edge $(u,v) \in E$: set weight $w_{uv} = -1$ (we want to minimize these cut edges, so penalize cutting them in a max objective).

3. For each pair $(i,j)$ with $i < j$: add a penalty edge with weight $P > 0$. These reward balanced partitions — a balanced cut of the complete graph gives $|A| \cdot |B| = (n/2)^2$ cut edges, which is maximal.

4. Equivalently, the combined objective is:

$$\text{maximize} \quad P \cdot |A| \cdot |B| - \text{cut}_G(A, B)$$

For $P$ large enough, this forces $|A| = |B| = n/2$ and then minimizes the original cut.

Solution extraction: The MaxCut partition of $G'$ gives the minimum bisection of $G$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vertices	$n$
num_edges	$\binom{n}{2}$ (complete graph with combined weights)

Validation Method

Closed-loop testing: solve GraphPartitioning by brute-force, solve the reduced MaxCut, and verify the extracted partition matches the optimal bisection.

Example

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

MaxCut graph $G'$: 6 vertices, $\binom{6}{2} = 15$ weighted edges. Original edges get weight $-1$; all pairs get penalty weight $P = 10$. Combined: original edge $(u,v)$ has weight $10 - 1 = 9$; non-edge pair has weight $10$.

Optimal partition $A = {0,1,2}$, $B = {3,4,5}$:

• Cut value: $9 \cdot 3 + 10 \cdot 6 = 27 + 60 = 87$ (3 original crossing edges at weight 9, 6 non-edge cross-pairs at weight 10)

An unbalanced partition $|A| = 2, |B| = 4$ would cut fewer complete-graph edges ($2 \times 4 = 8 < 9$ cross-pairs), reducing the penalty term and making it suboptimal.