A tight upper bound on the probabilistic embedding of series-parallel graphs
Yuval Emek, David Peleg · Symposium on Discrete Algorithms · 2006
In [6] it is shown that every graph can be probabilistically embedded into a distribution over its spanning trees with expected distortion O(log2n log log n), narrowing the gap left by [1], where a lower bound of Ω(log n) is established. This lower bound holds even for the class of series-parallel graphs as proved in [8]. In this paper we close this gap for series-parallel graphs, namely we prove that every n-vertex series-parallel graph can be probabilistically embedded into a distribution over its spanning trees with expected stretch O(log n) for every two vertices. We gain our upper bound by presenting a polynomial time probabilistic algorithm that constructs spanning trees with low expected stretch. This probabilistic algorithm can be derandomized to yield a deterministic polynomial time algorithm for constructing a spanning tree of a given series-parallel graph G, whose communication cost is at most O(log n) times larger than that of G.