[Rule] GraphPartitioning to ILP

[zazabap]

Source: GraphPartitioning
Target: ILP
Motivation: Enables solving graph bisection via ILP solvers; standard formulation used in VLSI partitioning tools.
Reference: Brunetta, Conforti & Rinaldi, 1997

Reduction Algorithm

Notation:

• Source: undirected graph $G = (V, E)$, $n = |V|$ (even), $m = |E|$
• Target: ILP with binary variables, linear constraints, and a minimize objective

Variable mapping:

Partition variables: $x_i \in {0, 1}$ for each vertex $i \in V$ ($x_i = 1$ if $i \in B$).

Edge-crossing variables: $y_{uv} \in {0, 1}$ for each edge $(u, v) \in E$ ($y_{uv} = 1$ if the edge crosses the partition).

Constraints:

1. Balance: $\sum_{i \in V} x_i = n/2$

2. Crossing detection (for each edge $(u, v) \in E$):

   • $y_{uv} \geq x_u - x_v$
   • $y_{uv} \geq x_v - x_u$

Objective: minimize $\sum_{(u,v) \in E} y_{uv}$

Solution extraction: $A = {i : x_i = 0}$, $B = {i : x_i = 1}$.

Size Overhead

Target metric (code name)	Polynomial (using symbols above)
num_vars	$n + m$
num_constraints	$2m + 1$

Validation Method

Closed-loop testing: solve GraphPartitioning by brute-force, solve the reduced ILP, and verify that both give the same optimal cut size.

Example

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

ILP: 15 variables ($x_0, \ldots, x_5$ + 9 edge variables), 19 constraints (18 crossing + 1 balance).

Optimal: $x = (0,0,0,1,1,1)$, $A = {0,1,2}$, $B = {3,4,5}$, objective $= 3$ crossing edges.