Algorithm Design And Analysis Of Large Scale Steiner Tree Problem

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(the11th 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,there are still a large number of difficult instances that have not yet been solved.These instances are divided into two categories,one is the instance with a very large scale of the graph,and the other is the instance with uniform edge weight on the graph.Existing algorithms typically encounter difficulty for solving large Steiner tree instances,that is,graphs with a large number of vertices and terminals.Therefore,we propose 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.In order to solve the Steiner tree problem with uniform edge weight,we study an effective iterative local search algorithm.We design an efficient strategy to reduce the time complexity of Steiner-vertex-elimination and Steiner-vertex-exchange according to the feature of uniform edge weight.The iterative local search algorithm also includes a new neighborhood generation method,ie.,Steiner-edge-vertex exchange.We conduct experiments on a wide range of well-known instances and confirm that our algorithm competes favorably with other state-of-the-art algorithms.Further experiments also validate the effectiveness of the proposed techniques.