Massively Parallel Approximate Steiner Tree Algorithms
摘要
This work studies the approximate Steiner tree problem in the Massively Parallel Computation (MPC) model where each machine has \(O(n^{\sigma })\) memory and \(\sigma \in (0,1)\) . n is the number of nodes in a graph. We focus on the undirected connected weighted graphs with shortest path diameter D and a terminal set S. The shortest path diameter is the minimum number of edges required for the shortest path constituting a weighted graph’s diameter. The straightforward approach takes O(n) rounds and \(O(n^{3-\sigma /2})\) total memory, which is inefficient. To simplify the straightforward approach and reduce the round complexity, we design a constant-round subroutine to compute the routing table and combine algebraic strategies with recursive methods to compute the Steiner tree efficiently. By these techniques, we give the first parallel \(2(1-1/|S|)\) -approximate Steiner tree algorithm that requires \(O(\sigma ^{-1}\log n+D)\) rounds with the same memory size and the same approximation ratio. Moreover, we extend the straightforward approach to the MPC model with O(n) memory per machine, which takes \(O(\log n)\) rounds and significantly outperforms the existing algorithm [21] when \(D\gg O(\log n)\) .