Distributed Steiner Forest Construction

Abstract: Starting from the well-known minimum spanning tree (MST) problem, I'll introduce the more general problem of constructing Steiner Forests (SF). The setting will be CONGEST model we know from previous occasions. I'll revisit the classic results on MST and then move on to two new distributed algorithms for SF we submitted to PODC. One is a deterministic (2+eps)-approximation that is an approximate distributed variant of the so-called moat-growing algorithm. The other is a (much faster) randomized O(log n)-approximation based on a combination of a distributed construction of a metric tree embedding technique and a sparsification technique from previous work together with Boaz Patt-Shamir. I will also discuss lower bounds; the running time of the second algorithm is tight up to factor polylog n.