Improved Distributed Steiner Forest Construction Extended Abstract

We present new distributed algorithms for constructing a Steiner Forest in the congest model. Our deterministic algorithm finds, for any given constant ε> 0, a (2 + ε)-approximation in Õ(sk +√min {st, n}) rounds, where s is the shortest path diameter, t is the number of terminals, k is the number of terminal components in the input, and n is the number of nodes. Our randomized algorithm finds, with high probability, an O(logn)-approximation in time Õ(k + min {s,√n} + D), where D is the unweighted di-ameter of the network. We also prove a matching lower bound of Ω̃(k+min {s,√n}+D) on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and ob-tained either an O(logn)-approximation in Õ(sk) time, or an O(1/ε)-approximation in Õ((√n+ t)1+ε +D) time. 1