[Model] GraphPartitioning

[zazabap]

Motivation

Core NP-hard problem in VLSI chip design, parallel computing, and scientific simulation. Standard tools (METIS, KaHIP, Scotch) are used across the semiconductor and HPC industries. Has natural reductions to ILP, QUBO, MaxCut, and SpinGlass.

Definition

Name: GraphPartitioning (Minimum Bisection)
Reference: Garey, Johnson & Stockmeyer, 1976; Bui & Jones, 1992

Given an undirected graph $G = (V, E)$ with $|V| = n$ (even), partition $V$ into two disjoint sets $A$ and $B$ with $|A| = |B| = n/2$, minimizing the number of edges crossing the partition:

$$\text{cut}(A, B) = |{(u, v) \in E : u \in A, v \in B}|$$

Variables

• Count: $n$ (one variable per vertex)
• Per-variable domain: binary ${0, 1}$
• Meaning: $x_i = 0$ if vertex $i \in A$, $x_i = 1$ if vertex $i \in B$

Schema (data type)

Type name: GraphPartitioning
Variants: balanced bisection (equal halves), $k$-way partitioning, weighted vertices/edges

Field	Type	Description
graph	SimpleGraph	The undirected graph $G = (V, E)$

Problem Size

Metric	Expression	Description
num_vertices	$n$	Number of vertices
num_edges	$m$	Number of edges

Complexity

• Decision complexity: NP-complete (Garey, Johnson & Stockmeyer, 1976)
• Best known exact algorithm: $O(2^n)$ brute-force; practical solvers use branch-and-bound with spectral lower bounds
• Approximation: $O(\sqrt{\log n})$-approximation (Arora, Rao & Vazirani, 2009)
• References: Garey et al. 1976; Arora, Rao & Vazirani 2009

Extra Remark

METIS and its variants are the industry standard for graph partitioning in VLSI layout, finite element mesh decomposition, and distributed computing. The problem is closely related to MaxCut (which maximizes rather than minimizes the cut) and SpinGlass (via the Ising model).

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing to integer programming, through a new GraphPartitioning → ILP rule issue (to be filed).

Bruteforce: enumerate all $\binom{n}{n/2}$ balanced partitions, count cut edges for each, return minimum.

Example Instance

$n = 6$ vertices, $m = 9$ edges:

0 --- 1
|\ /|
| X  |
|/ \|
2 --- 3
|     |
4 --- 5

Edges: $(0,1), (0,2), (1,2), (1,3), (2,3), (2,4), (3,4), (3,5), (4,5)$

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

The 3 crossing edges are $(1,3), (2,3), (2,4)$. Compare: worst partition has cut $= 7$.