TBGMax: leveraging two-boundary graph pattern for lossless maximum-flow acceleration

The maximum-flow (max-flow) problem is a classic combinatorial optimization problem that has been used in many kinds of applications.The existing methods accelerate by contracting large-size subgraphs, but can only obtain approximated results with significant deviations. To address the problem, we propose a two-boundary graph pattern-based contraction algorithm for lossless max-flow acceleration (TBGMax). TBGMax can obtain accurate results by contracting two-boundary graphs of any size into edges, only involves connectivity information and does not need any extra information such as the edge capacity and local topology. TBGMax can accelerate even further by excluding irrelevant nodes. Random and real graphs-based simulations show that TBGMax can accelerate classic max-flow algorithm by up to 75.1 times in benchmark problem families and up to 22.3 times in real-world road networks, and at best only involve an average of 0.002% of the nodes in a graph.