Exact Minimum Cuts in Hypergraphs at Scale
Adil Chhabra, Christian Schulz, Bora Uçar, Loris Wilwert · Society for Industrial and Applied Mathematics eBooks · 2026
The hypergraph minimum cut problem aims to partition the vertices of a hypergraph into two non-empty parts while minimizing the total weight of hyperedges crossing the cut. This problem lies at the core of many tasks in network reliability, VLSI placement, and community detection. We introduce HeiCut, the first algorithm that makes exact minimum cut computation feasible for both weighted and unweighted instances at scales of hundreds of millions of vertices. HeiCut presents seven exact reduction rules that provably preserve the minimum cut, and an optional heuristic contraction based on label propagation that shrinks complex and persistent structures. When no further reductions are possible, the remaining instance is solved exactly with a known algorithm. Our extensive evaluation on more than 500 real-world hypergraphs reveals that the exact reductions alone already expose the minimum cut (i.e., the residual collapses to a single vertex or has no hyperedges) in over 85% of instances. Across all instances, HeiCut solves over twice as many instances as the state-of-the-art within set computational limits, and is up to five orders of magnitude faster. Thus, HeiCut significantly advances hypergraph minimum cut computation in real-world, largescale scenarios.