Accelerate minimum cut calculation by tree-cut mapping with local pruning

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.

Automated summary

This article proposes a new approximation algorithm for the minimum cut (min-cut) problem in undirected graphs, which can accelerate existing methods by up to 6 orders of magnitude with limited preprocessing overhead. By checking and recording the cut values of various traversal trees, the algorithm estimates the upper bound of the min-cut value between any pair of nodes. Experimental results show that even the serial implementation of the algorithm achieves a larger acceleration ratio compared to existing methods.