Greedy algorithm works exactly for certain weighted minimum 3-cut problems
When is greedy exact for weighted minimum 3-cut?
Data Structures and Algorithms
Summary
Finding the best way to split a network into three parts with the smallest total cut cost can be hard. The authors studied when a simple greedy method finds the exact best split in weighted networks. They showed this happens if the weights between two parts of a best split are at least the network's edge connectivity. This finding generalizes earlier results and also applies to splitting into more than three parts. Their proofs and some counterexamples were checked using formal software verification.
What this means in practice
- •For network engineers: Identify network splits that can be optimally found with a simple greedy approach when edge weights meet connectivity thresholds.
- •For graph algorithm developers: Design improved algorithms for minimum k-cut problems by incorporating conditions under which greedy methods are exact.
A theory result. No direct application yet.
Authors
Armando Rodado Amaris
Abstract
The greedy algorithm for minimum 3-cut splits a global minimum-weight cut and then the cheaper of its two sides; it is a tight $4/3$-approximation. We show that it is exact, from every global minimum-weight cut, whenever some optimal 3-partition has two parts joined by total weight at least the weighted edge connectivity $λ$. This extends both theorems of Hochbaum and Shmoys from unweighted planar graphs to all weighted graphs, recovers the $4/3$ bound, and generalizes to minimum $k$-cut with a one-paragraph proof. The remaining hard instances have all pair weights below $λ$; for them we prove a merge lemma for Gomory-Hu sides. Finally, we give a 7-vertex graph with a unique Gomory-Hu tree whose unique optimal 3-partition contains no side of that tree, so the first stage of Kapoor's algorithm does not suffice on its own. The main theorem, the 4/3 bound, the merge lemmas and the counterexample are verified in the Lean 4 proof assistant.