High‐Speed Minimum Cut Approximation in Dense Graph Using Compacted Pruned Tree

ABSTRACT Solutions for minimum cut of a graph have been widely used in many applications, but existing acceleration methods have almost reached their limits by optimizing algorithm logic or reducing graph data. Given the mapping between traversal trees and cuts in a graph, we propose to deal with the problem from a new perspective, namely, cut enumeration. The algorithm enumerates the cuts using the depth‐first traversal tree, locates the optimal tree per node with the smallest local cut, and compacts them for acceleration. Any node pair can be separated by compacted trees containing only one of them. Its serial implementation is validated to be effective in obtaining the accurate solution for 99.9% or more pairs of vertices in a graph. Its calculation time per pair is as low as a thousandth of that of the most efficient existing method, that is, several microseconds in a graph with tens of millions of edges using an off‐shelf computing node, thus serving as an effective heuristic for min‐cut approximation.