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

Abstract

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.

Keywords:

• Boundary node
• maximum flow
• graph contraction
• overlay
• parallel algorithm

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This paper was supported by the National Natural and Science Foundation of China [61702162,62006071,61772173,61973104,61803146], the Key Laboratory of Grain Information Processing and Control(Henan University of Technology), the Ministry of Education [KFJJ-2016-104], Science and technology project of science and technology department of Henan province [202102210148], Backbone Teacher Training Program of Henan University of Technology [2012012], Young Backbone Teacher Training Program of Henan Higher Education [2018GGJS066], Plan For Scientific Innovation Talent of Henan University of Technology (2018RCJH07,2018QNJH26), Doctor Foundation of Henan University of Technology [2017025], Natural Science Foundation of the Henan Province [152102210068], National Key Research and Development Program of China [2017YFD0401001], Program for Science and Technology Innovation Talents in Universities of Henan Province [19HASTIT027], Key Science and Technology Research Project of Education Department Henan Province [18A520026].