A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs

The Steiner tree problem aims to determine a minimum edge-weighted tree spanning a given set of terminal vertices from a given graph. As a popular model for numerous practical applications, the problem has been the object of two important competitions (the 11th DIMACS Challenge in 2014 and the 3rd PACE Competition in 2018). A number of practical algorithms have been developed for solving this computationally challenging problem in the past decade. However, existing algorithms typically encounter difficulty for solving large Steiner instances, i.e., graphs with a high number of vertices and terminals.In this paper, we present a novel partition-and-merge algorithm for effectively solving this problem in large graphs. The algorithm breaks the input graph into small subgraphs and then merges the subgraphs in a bottom-up manner. During the merging procedure, partial Steiner trees in the subgraphs are also created and optimized by an efficient local optimization. When the merging procedure ends, the algorithm terminates and reports the final solution for the input graph.We assess the algorithm on a wide range of benchmark instances, showing that the algorithm outperforms the winners of DIMACS and PACE challenges on large instances and competes favorably with them on small or middle-sized instances