[Model] MinimumMultiwayCut

[hmyuuu]

Motivation

Fundamental graph partitioning problem that generalizes the minimum s-t cut (k=2, polynomial) to $k \geq 3$ terminals (NP-hard); important in VLSI design, image segmentation, and network design, with a direct ILP formulation.

Definition

Name: MinimumMultiwayCut
Reference: Dahlhaus, Johnson, Papadimitriou, Seymour & Yannakakis (1994), SIAM J. Comput.

Given an undirected weighted graph $G = (V, E, w)$ where $V$ is the vertex set, $E$ is the edge set, and $w : E \to \mathbb{R}_{>0}$ assigns a positive weight to each edge, and a set of $k$ terminal vertices $T = {t_1, t_2, \ldots, t_k} \subseteq V$, find a minimum-weight set of edges $C \subseteq E$ such that no two terminals remain in the same connected component of $G' = (V, E \setminus C)$.

Equivalently, $C$ must induce a partition of $V$ into $k$ disjoint subsets $V_1, \ldots, V_k$ with $t_i \in V_i$, minimizing

$$\sum_{e \in C} w(e) = \sum_{\substack{(u,v) \in E \ \exists, i \neq j: u \in V_i,, v \in V_j}} w(u, v)$$

Variables

• Count: $m = |E|$ (one binary variable per edge)
• Per-variable domain: binary ${0, 1}$
• Meaning: $x_e = 1$ if edge $e \in E$ is in the cut (removed); $x_e = 0$ otherwise. A configuration is feasible if removing the cut edges ${e \mid x_e = 1}$ disconnects every pair of terminals.

Schema (data type)

Type name: MinimumMultiwayCut
Variants: graph topology (SimpleGraph, weighted or unweighted)

Field	Type	Description
graph	SimpleGraph	the graph $G = (V, E)$
terminals	Vec<usize>	terminal vertex indices $T = {t_1, \ldots, t_k} \subseteq V$
weights	Vec<W>	edge weights $w_e$ for each $e \in E$ in the same order as the graph's edge list (unweighted variant uses unit weights)

Complexity

• Best known exact algorithm: $O^*(1.84^k)$ (suppressing polynomial factors in $n = |V|$) by Cao, Chen & Fan (2013), where $k = |T|$ is the number of terminals; with explicit polynomial factors $O(1.84^k \cdot n^3)$
• References: Cao, Chen & Fan (2013), FCT 2013; arXiv:1711.06397; IPL journal version

Extra Remark

The case $k = 2$ is the classical minimum $s$-$t$ cut problem, solvable in polynomial time via max-flow. For $k \geq 3$ on general graphs, the problem is NP-hard (Dahlhaus et al. 1994); it remains NP-hard even for unit weights and planar graphs. The algorithm of Cao et al. (2013) improved upon earlier $O^(2^k)$ and $O^(4^k)$ results using submodular functions on isolating cuts. A $(2 - 2/k)$-approximation is achievable in polynomial time by taking the union of the $k-1$ cheapest isolating cuts (Dahlhaus et al. 1994). See also the PAAL library implementation: https://paal.mimuw.edu.pl/docs/multiway_cut.html

How to solve

• It can be solved by (existing) bruteforce.
• It can be solved by reducing the integer programming, through #issue-number (please file a new issue it is not exist).
• Other, refer to ...

Example Instance

$n = 5$ vertices $V = {0,1,2,3,4}$, terminals $T = {0, 2, 4}$, and 6 edges with weights:

Edge	Weight
(0, 1)	2
(1, 2)	3
(2, 3)	1
(3, 4)	2
(0, 4)	4
(1, 3)	5

Optimal multiway cut: remove edges ${(0,1), (0,4), (3,4)}$ with total weight $2 + 4 + 2 = \mathbf{8}$.

After removal, the connected components are ${0}$, ${1, 2, 3}$, ${4}$ — each terminal is in a distinct component. Verified by exhaustive search over all $2^6 = 64$ edge subsets: no lighter feasible cut exists.

[zazabap]

Issue Quality Check — Model

Check	Result	Details
Usefulness	✅ Pass	Novel problem, generalizes min s-t cut
Non-trivial	✅ Pass	Distinct terminal-separation constraints
Correctness	⚠️ Warn	References verified; complexity parameterization needs clarification
Well-written	⚠️ Warn	Minor weight storage and complexity variable issues

Overall: 2 passed, 0 failed, 2 warnings

---

Usefulness

No MinimumMultiwayCut exists in the codebase. The problem generalizes classical min s-t cut from k=2 (polynomial) to k≥3 (NP-hard). Concrete applications in VLSI design, image segmentation, and network partitioning. Planned reductions to ILP (#185) and QUBO (#186) connect to existing models.

Non-trivial

Genuinely distinct from all existing problems:

• vs. MaxCut: MaxCut maximizes cut weight over a bipartition with no terminal constraints. MinimumMultiwayCut minimizes subject to k-terminal separation.
• vs. MinimumVertexCover: Different objective (edge removal for terminal separation vs. vertex selection for edge coverage).
• vs. KColoring: Satisfaction problem about vertex labeling, not edge removal or weight minimization.

Correctness

Reference	Status	Notes
Dahlhaus, Johnson, Papadimitriou, Seymour & Yannakakis (1994), SIAM J. Comput. 23, pp. 864–894	✅ Verified	"The Complexity of Multiterminal Cuts." NP-hardness for k ≥ 3 and (2 - 2/k)-approximation confirmed.
Cao, Chen & Fan (2013), FCT 2013, LNCS 8070	✅ Verified	O*(1.84^k) parameterized algorithm confirmed. Also published in IPL vol. 114, pp. 167–173, 2014.
arXiv:1711.06397	✅ Verified	Extended arxiv version of the same paper.

Complexity clarification needed:

The O*(1.84^k) bound is FPT — parameterized by k (number of terminals), not by problem size. For the declare_variants! macro, the codebase requires complexity in terms of getter-method variables like num_vertices or num_edges:

• If k can be up to n, the bound becomes O*(1.84^n), but this is loose.
• The naive exact algorithm is O(2^m) (enumerate edge subsets).
• Recommendation: Add a num_terminals() getter and use "1.84 ^ num_terminals" as the complexity string, or use "2 ^ num_edges" as the worst-case bound. The full FPT bound is O(1.84^k · n³).

Example verified: The optimal multiway cut of weight 8 (edges {(0,1), (0,4), (3,4)}) producing components {0}, {1,2,3}, {4} was confirmed correct by exhaustive search over all 2⁶ = 64 edge subsets.

Well-written

All required sections present. The example is well-constructed (5 vertices, 3 terminals, 6 edges).

Minor issues:

• Weight storage: The Schema stores weights in a separate Vec<W> field. Other graph problems in the codebase (MaximumIndependentSet, MaxCut, etc.) parameterize by W: WeightElement and store weights within the graph structure using inherent methods (weights(), set_weights()). Should align with this pattern.
• Naming: "MinimumMultiwayCut" correctly uses the Minimum prefix ✅

Recommendations

• Clarify complexity string for declare_variants! — suggest "1.84 ^ num_terminals" with a num_terminals() getter
• Align weight storage with existing graph problem patterns (W: WeightElement + inherent methods)
• Consider filing an ILP reduction issue (the motivation mentions "a direct ILP formulation" but "How to solve" doesn't check the ILP box — though [Rule] MinimumMultiwayCut to ILP #185 already exists)