In the Steiner Forest problem, we are given an undirected graph with non-negative weights for edges, a set of pairs of vertices, called terminals, and the goal is to find the minimum cost subgraph that connects each of the terminal pairs together. There exist several sequential heuristic and approximation algorithms for the Steiner Forest problem. In practice, the primal-dual 2-approximation algorithm is one of the fastest and obtains solutions that are very close to the optimal solution. In this paper, we design a practical parallel approximation algorithm based on the primal-dual sequential algorithm. The parallel algorithm maintains the approximation guarantees of the sequential primal-dual algorithm and it is specifically designed for execution on multi-core computers. We implement and run the parallel algorithm on a multi-core system with a large number of cores and perform an extensive experimental performance analysis on randomly generated graphs. The results show that our proposed parallel approximation algorithm achieves a significant speedup with respect to the sequential primal-dual algorithm.

Abstract In the Steiner forest problem, we are given a set of terminal pairs and need to find the minimum cost subgraph that connects each of the terminal pairs together. Motivated by the recent work on greedy approximation algorithms for the Steiner forest, we provide efficient implementations of existing approximation algorithms and conduct a thorough experimental study to characterize their performance. We consider several approximation algorithms: the influential primal‐dual 2‐approximation algorithm due to Agrawal, Klein, and Ravi, the greedy algorithm due to Gupta and Kumar, and a randomized algorithm based on probabilistic approximation by tree metrics. We also consider the simplest heuristic greedy algorithm for the problem, which picks the closest unconnected pair of terminals and connects it using the shortest path between the terminals in the current graph. To characterize the performance of the algorithms, we created a new library with more than one thousand Steiner forest problem instances and conducted an extensive experimental analysis on those instances. Our analysis reveals that for the majority of instances the primal‐dual algorithm is the fastest among all the algorithms considered here, and obtains solutions that are very close to the optimal solutions obtained by solving the integer program formulation of the problem.