High-precision ultra-fast minimum cut approximation through aggregated hash of cut collection.

Due to the wide application of s - t minimum cut (min-cut) in various scenarios, many acceleration algorithms have been proposed to solve it. However, the query times of the acceleration algorithms currently available are still high in large-scale graphs, rendering them useless in frequently solving scenarios. We re-examine the min-cut problem from a novel perspective of cut collection hash. By extracting aggregated hashes of mapped cut collections in one-dimensional space, a Monte Carlo-like method is used to quickly compare them and estimate the minimum cut between any two nodes with low computational effort and high accuracy. After the graph is preprocessed using a few hundred depth-first traversals, the time complexity of the min-cut solution can be logarithmic in terms of the average degree and capacity of the graph. Experiments on large-scale graphs show that compared to the fastest exact algorithm, the proposed algorithm can increase the speed of the min-cut solution by up to seven orders of magnitude, when only a few mathematical comparisons per pair are needed to obtain exact min-cut values of no less than 99.9% node pairs. • The minimum cut problem is revisited from a novel angle of cut collection. • It is the first algorithm that finds the minimum cut through comparing aggregated hash of cut collections. • Cut collections are mapped to one-dimensional space to obtain fingerprint facilitating fast comparison. • The preprocessing overhead can be as low as limited passes of depth-first traversals to obtain 99.9% exact minimum cut values. • The average acceleration ratio to the fastest minimum cut implementation can be more than 7 orders of magnitude. [ABSTRACT FROM AUTHOR]