[Rule] MinimumMultiwayCut to ILP

[hmyuuu]

Source: MinimumMultiwayCut
Target: ILP
Motivation: Enables exact solving of the minimum multiway cut on any backend ILP solver; serves as the canonical exact formulation for testing and validation.
Reference: Chopra & Owen (1996), Mathematical Programming 73, pp. 7–30; Călinescu, Karloff & Rabani (2000), J. Comput. Syst. Sci. 60(3); Illinois lecture notes §7

Reduction Algorithm

Notation:

• Source: graph $G = (V, E, w)$ with $n = |V|$ vertices, $m = |E|$ edges, edge weights $w_e \in \mathbb{R}{>0}$, and $k = |T|$ terminal vertices $T = {t_0, t_1, \ldots, t{k-1}} \subseteq V$.
• Target: ILP with $kn + m$ binary variables.

Variable mapping:

Introduce two families of binary ILP variables (flattened into a single vector):

• $y_{iv} \in {0,1}$ for each $i \in {0,\ldots,k-1}$ and $v \in V$, at index $i \cdot n + v$: equals $1$ if vertex $v$ is assigned to the component of terminal $t_i$.
• $x_e \in {0,1}$ for each edge $e \in E$, at index $kn + e_{\text{idx}}$: equals $1$ if edge $e$ is in the cut.

Bounds (fixing terminals):

• $y_{i,t_i} = 1$ for each $i$ (terminal $t_i$ is fixed to its own component); implemented as bounds $[1, 1]$.
• $y_{j,t_i} = 0$ for all $j \neq i$ (terminal $t_i$ cannot belong to another component); implemented as bounds $[0, 0]$.
• All other $y_{iv}$ and $x_e$: binary bounds $[0, 1]$.

Constraints:

1. Partition constraint (equality, $n$ constraints): each vertex belongs to exactly one component:
   $$\sum_{i=0}^{k-1} y_{iv} = 1 \quad \forall v \in V$$

2. Edge-cut lower bounds (inequality, $2km$ constraints): if the endpoints of edge $e = (u, v)$ are in different components, then $x_e = 1$:
   $$x_e \geq y_{iu} - y_{iv} \quad \text{and} \quad x_e \geq y_{iv} - y_{iu} \quad \forall e = (u,v) \in E,\ i \in {0,\ldots,k-1}$$

Objective: Minimize total cut weight:
$$\min \sum_{e \in E} w_e \cdot x_e$$

Solution extraction: A solution to the ILP yields $x_e^* \in {0,1}$; the multiway cut is ${e \in E \mid x_e^* = 1}$ with cost $\sum_e w_e x_e^*$.

Size Overhead

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

Validation Method

• Compare ILP optimal value against brute-force multiway cut on small instances (e.g., $n \leq 6$, $k = 3$).
• Cross-check against PAAL library implementation: https://paal.mimuw.edu.pl/docs/multiway_cut.html
• Verify that the partition induced by $y_{iv}^$ matches the cut edges $x_e^$: for every cut edge $e=(u,v)$ in the solution, $u$ and $v$ must be in different components.

Example

Source instance (same as in model issue #184):

• $n = 5$ vertices $V = {0,1,2,3,4}$, $k = 3$ terminals $T = {0, 2, 4}$, $m = 6$ edges:

Edge index	$(u, v)$	$w_e$
0	(0, 1)	2
1	(1, 2)	3
2	(2, 3)	1
3	(3, 4)	2
4	(0, 4)	4
5	(1, 3)	5

ILP instance: $kn + m = 3 \cdot 5 + 6 = 21$ binary variables, $n + 2km = 5 + 2 \cdot 3 \cdot 6 = 41$ constraints.

Variable layout:

• $y_{0,v}$: variables 0–4 (component 0, one per vertex); fixed: $y_{0,0}=1$, $y_{0,2}=0$, $y_{0,4}=0$
• $y_{1,v}$: variables 5–9 (component 1); fixed: $y_{1,0}=0$, $y_{1,2}=1$, $y_{1,4}=0$
• $y_{2,v}$: variables 10–14 (component 2); fixed: $y_{2,0}=0$, $y_{2,2}=0$, $y_{2,4}=1$
• $x_e$: variables 15–20 (edge cut indicators)

Objective: minimize $2x_0 + 3x_1 + x_2 + 2x_3 + 4x_4 + 5x_5$.

Optimal ILP solution: $x_0 = x_3 = x_4 = 1$ (all others 0), yielding objective $2 + 2 + 4 = \mathbf{8}$.

Corresponding partition: $V_0 = {0}$, $V_1 = {1, 2, 3}$, $V_2 = {4}$. Each terminal is in its own component. Verified to match brute-force optimal from issue #184.