Empirical study on sufficient numbers of minimum cuts in strongly connected directed random graphs. Issue 1 (5th May 2020)

• Record Type: Journal Article
• Authors: Chang, Eric; Cheng, C. K.; Gupta, Anushka; Hsu, Po‐Ya; Moffitt, Amanda; Ren, Alissa; Tsaur, Irene; Wang, Samuel
• Is Part Of: Networks. Volume 76:Issue 1(2020)
• Page Start: 106
• Page End: 121
• Publication Date: 2020-05-05
• Subjects: all‐pairs minimum cut -- directed graphs -- flow cut -- graph partitioning -- minimum cuts -- network flow -- replication cut -- symmetric cuts; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21943
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: We focus on the all‐pairs minimum cut (APMC) problem, a graph partitioning problem whose solution requires finding the minimum cut for every pair of nodes in a given graph. While it is solved for undirected graphs, a solution for APMC in directed graphs still requires an O ( n 2 ) brute force approach. We show that the empirical number of distinct minimum cuts in randomly generated strongly connected directed graphs is proportional to n rather than the theoretical value of n 2, suggesting the possibility of an algorithm which finds all minimum cuts in less than O ( n 2 ) time. We also provide an example of the strict upper bound on the number of cuts in graphs with three nodes. We model the distributions with the Generalized extreme value (GEV) distribution and enable the possibility of using a GEV distribution to predict the probability of achieving a certain number of minimum cuts, given the number of nodes and edges. Finally, we contribute to the notion of symmetric cuts by showing that there can be O ( n 2 ) symmetric cuts in graphs when node replication is allowed.