Approximating Directed Telephone Multicast

Abstract

In the telephone model a message starts at a source vertex, and in every round each informed vertex may call one neighbour. Telephone multicast asks for a schedule that informs a given set of $k$ terminals in the fewest rounds. On directed graphs, the best known ratio for this problem was $\tilde{O}(\sqrt{k})$, due to Elkin and Kortsarz and to Hathcock, Kortsarz and Ravi. For every integer $\ell \ge 2$, we give a deterministic combinatorial algorithm with running time $n^{O(\ell )}$ that computes a schedule of length $O({\ell }^3\log k)\cdot (\mathrm{OPT}+k^{1/\ell })$, where $n$ is the number of vertices and $\mathrm{OPT}$ the optimum. Since $\mathrm{OPT}\ge {\log }_2(k+1)$, this gives ratio $O(k^{\epsilon })$ in time $n^{O(1/\epsilon )}$ for every fixed $\epsilon >0$, and ratio $O({\log }^{4}k)$ in quasi-polynomial time. The method rests on jump trees with additive vertex loads, a height reduction that bounds the load of every vertex, and a recursive greedy algorithm with an exponential potential. We also show that directed multicast is a special case of the degree-bounded directed Steiner tree problem on a time-expanded digraph. With known algorithms for that problem this gives randomized ratios $O({\log }^{2}n)$ in time $n^{O(\log n)}$ and $O(n^{\epsilon })$ in time $n^{O(1/\epsilon )}$, which, unlike ours, grow with $n$. On the hardness side, directed multicast stays $(1-\epsilon )\ln k$-hard even when $\mathrm{OPT}=O(\log k)$, the regime in which the previous algorithms were weakest.