{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T04:19:28Z","timestamp":1761193168082,"version":"build-2065373602"},"reference-count":23,"publisher":"MDPI AG","issue":"10","license":[{"start":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T00:00:00Z","timestamp":1760918400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>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\u2013sink 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\u2013min 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\u2013Hu 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.<\/jats:p>","DOI":"10.3390\/a18100665","type":"journal-article","created":{"date-parts":[[2025,10,20]],"date-time":"2025-10-20T13:54:41Z","timestamp":1760968481000},"page":"665","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Recursive Solution to the Global Maximum Minimum Cut Problem with a Fixed Sink"],"prefix":"10.3390","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2571-1979","authenticated-orcid":false,"given":"Xiaoyao","family":"Huang","sequence":"first","affiliation":[{"name":"China Telecom Cloud Computing Research Institute, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shuo","family":"Quan","sequence":"additional","affiliation":[{"name":"China Telecom Cloud Computing Research Institute, Beijing 100083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Wu","sequence":"additional","affiliation":[{"name":"China Telecom Cloud Computing Research Institute, Beijing 100083, China"},{"name":"Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,10,20]]},"reference":[{"unstructured":"Kleinberg, J., and Tardos, E. (2006). Algorithm Design, Pearson Education.","key":"ref_1"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1137\/0109047","article-title":"Multi-terminal network flows","volume":"9","author":"Gomory","year":"1961","journal-title":"J. Soc. Ind. Appl. Math."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"399","DOI":"10.4153\/CJM-1956-045-5","article-title":"Maximal flow through a network","volume":"8","author":"Ford","year":"1956","journal-title":"Can. J. Math."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","article-title":"Theoretical improvements in algorithmic efficiency for network flow problems","volume":"19","author":"Edmonds","year":"1972","journal-title":"J. ACM (JACM)"},{"key":"ref_5","first-page":"1277","article-title":"Algorithm for solution of a problem of maximum flow in networks with power estimation","volume":"11","author":"Dinic","year":"1970","journal-title":"Sov. Math. Dokl."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/48014.61051","article-title":"A new approach to the maximum-flow problem","volume":"35","author":"Goldberg","year":"1988","journal-title":"J. ACM (JACM)"},{"doi-asserted-by":"crossref","unstructured":"Orlin, J.B. (2013, January 1\u20134). Max flows in O (nm) time, or better. Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, Palo Alto, CA, USA.","key":"ref_7","DOI":"10.1145\/2488608.2488705"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1145\/234533.234534","article-title":"A new approach to the minimum cut problem","volume":"43","author":"Karger","year":"1996","journal-title":"J. ACM (JACM)"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1006\/jagm.1994.1043","article-title":"A faster algorithm for finding the minimum cut in a graph","volume":"17","author":"Hao","year":"1994","journal-title":"J. Algorithms"},{"unstructured":"Singla, A., Hong, C.Y., Popa, L., and Godfrey, P.B. (2012, January 25\u201327). Jellyfish: Networking data centers, randomly. Proceedings of the USENIX NSDI, San Jose, CA, USA.","key":"ref_10"},{"key":"ref_11","first-page":"343","article-title":"Scalable flow-based networking with DiffServ","volume":"38","author":"Loukissas","year":"2008","journal-title":"ACM SIGCOMM Comput. Commun. Rev."},{"key":"ref_12","first-page":"995","article-title":"Approximation algorithms for node-weighted buy-at-bulk network design","volume":"35","author":"Chekuri","year":"2006","journal-title":"SIAM J. Comput."},{"unstructured":"Karger, D.R. (1993, January 25\u201327). Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Austin, TX, USA.","key":"ref_13"},{"unstructured":"Bencz\u00far, A., and Karger, D.R. (1996, January 22\u201324). Approximating s-t minimum cuts in O(n2) time. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, Philadelphia, PA, USA.","key":"ref_14"},{"unstructured":"Ghaffari, M., Nowicki, K., and Thorup, M. (2020, January 22\u201326). Near-optimal minimum cut algorithms in the distributed, streaming, and MPC models. Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, Chicago, IL, USA.","key":"ref_15"},{"unstructured":"Geissmann, B., and Gianinazzi, L. (2018, January 16\u201318). Minimum cuts and network reliability in the congested clique model. Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, Vienna, Austria.","key":"ref_16"},{"doi-asserted-by":"crossref","unstructured":"Moitra, A. (2009, January 25\u201327). Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, Atlanta, GA, USA.","key":"ref_17","DOI":"10.1109\/FOCS.2009.28"},{"unstructured":"Chekuri, C., and Xu, C. (2017, January 16\u201319). Minimum cuts and sparsification in hypergraphs. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, Spain.","key":"ref_18"},{"unstructured":"Ghaffari, M., and Nowicki, K. (2018, January 7\u201310). Fully dynamic connectivity in O(logn(loglogn)2) amortized update time. Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA.","key":"ref_19"},{"unstructured":"Noe, A., Hagerup, T., and Dementiev, R. (2021, January 10\u201311). Practical minimum cut algorithms. Proceedings of the Meeting on Algorithm Engineering and Experiments (ALENEX), Virtual.","key":"ref_20"},{"unstructured":"Kale, S., Muthukrishnan, S., and Vassilvitskii, S. (2009, January 4\u20136). The geometry of graph streaming: Cut sketches and linear algebra. Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms, New York, NY, USA.","key":"ref_21"},{"doi-asserted-by":"crossref","unstructured":"Ahn, K.J., Guha, S., and McGregor, A. (2012, January 21\u201323). Graph sketches: Sparsification, spanners, and subgraphs. Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, Scottsdale, AZ, USA.","key":"ref_22","DOI":"10.1145\/2213556.2213560"},{"unstructured":"Gupta, A., Newman, I., Rabinovich, Y., and Sinclair, A. (2001, January 14\u201317). Cuts, trees and l1-embeddings. Proceedings of the 42nd IEEE Symposium on Foundations of Computer Science, Las Vegas, NV, USA.","key":"ref_23"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/10\/665\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,23]],"date-time":"2025-10-23T04:15:09Z","timestamp":1761192909000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/18\/10\/665"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,20]]},"references-count":23,"journal-issue":{"issue":"10","published-online":{"date-parts":[[2025,10]]}},"alternative-id":["a18100665"],"URL":"https:\/\/doi.org\/10.3390\/a18100665","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2025,10,20]]}}}