A Recursive Solution to the Global Maximum Minimum Cut Problem with a Fixed Sink

In graph theory and network design, the minimum cut is a fundamental measure of system connectivity and communication capacity. While prior research has largely focused on computing the minimum cut for a fixed source–sink pair, practical scenarios such as data center communication often demand a different objective: identifying the source node whose minimum cut to a designated sink is maximized. This task, which we term the Global Maximum Minimum Cut with Fixed Sink (GMMC-FS) problem, captures the goal of locating a high-capacity source relative to a shared sink node that aggregates multiple servers. The problem is of significant engineering importance, yet it is computationally challenging as it involves a nested max–min optimization. In this paper, we present a recursive reduction (RR) algorithm for solving the GMMC-FS problem. The key idea is to iteratively select pivot nodes, compute their minimum cuts with respect to the sink, and prune dominated candidates whose cut values cannot exceed that of the pivot. By recursively applying this elimination process, RR dramatically reduces the number of max-flow computations required while preserving exact correctness. Compared with classical contraction-based and Gomory–Hu tree approaches that rely on global cut enumeration, the proposed RR framework offers a more direct and scalable mechanism for identifying the source that maximizes the minimum cut to a fixed sink. Its novelty lies in exploiting the structural properties of the sink side of suboptimal cuts, which leads to both theoretical efficiency and empirical robustness across large-scale networks. We provide a rigorous theoretical analysis establishing both correctness and complexity bounds, and we validate the approach through extensive experiments. Results demonstrate that RR consistently achieves optimal solutions while significantly outperforming baseline methods in runtime, particularly on large and dense networks.