Accelerate minimum cut calculation by tree-cut mapping with local pruning. (November 2022)

• Record Type: Journal Article
• Authors: Wei, Wei; Hu, Qiuyuan; Yang, Weidong
• Is Part Of: Advances in engineering software. Volume 173(2022)
• Publication Date: 2022-11
• Subjects: Minimum cut -- Traversal tree -- Local pruning -- Graph preprocessing -- Acceleration; Computer-aided engineering -- Periodicals; Engineering -- Computer programs -- Periodicals; Engineering -- Software -- Periodicals; Periodicals; 620.0028553
• DOI: 10.1016/j.advengsoft.2022.103256
• Languages: English
• ISSNs: 0965-9978

Abstract

Abstract: As a fundamental problem in graph theory, the minimum cut (min-cut) problem and solutions have many applications in networking related researches. A new approximation algorithm for the problem in undirected graph is proposed that can accelerate existing method by up to 6 orders of magnitude, while the preprocessing overhead is just a limited number of depth-first traversing. In the algorithm, after checking and recording the cut values of various types of traversal trees, the good upper bound on the min-cut value between any node pair can be approximated using the minimal cut value of all related traversal trees, and the upper bound is very likely to be the exact value. The independence between different traversal passes makes it ready for further acceleration using parallelization. The traversal tree-cut mapping algorithm with local pruning (TCLP) is compared with other methods using random, scale-free and real-world graphs, the results show that even the serial implementation of TCLP can achieve far larger acceleration ratio than existing methods while obtaining exact min-cut value of 99.9% node pairs. The results also indicate that TCLP is general enough to not rely on any special local graph structure and is seldom affected by graph types, thus can be used as an effective supplement to the existing methods. Highlights: A new and ready-for-parallelization algorithm is proposed for maximum flow calculation. It is the first algorithm that utilizes the mapping from the set of all pruned traversal trees to the set of all cuts. The algorithm has low preprocessing overhead, high acceleration ratio and precision. The preprocessing overhead can be as low as just tens of depth-first traversals to provide the precision of 99.9%. The average acceleration ratio to the fastest max-flow implementation can be more than one million.