New algorithm improves message scheduling in directed networks
Approximating Directed Telephone Multicast
Data Structures and Algorithms
Summary
The paper addresses how to quickly spread a message from one source to many specific targets in a directed network where each informed node can call only one neighbor per round. The authors introduce a method that produces schedules with lengths close to the best possible, improving on previous algorithms, especially when the number of targets is large. Their approach uses new combinatorial structures called jump trees and a recursive greedy strategy, balancing speed and complexity. They also explore connections to existing network design problems and clarify computational hardness limits.
What this means in practice
- •For network schedulers: Design faster communication plans in directed networks where messages must reach multiple nodes under one-call-per-round constraints.
- •For distributed system engineers: Improve algorithms for efficiently broadcasting updates or instructions in systems modeled by directed graphs with strict communication limits.
Authors
Shahin Kamali, Seyed-Mohammad Seyed-Javadi
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\ge2$, 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^ε)$ in time $n^{O(1/ε)}$ for every fixed $ε>0$, and ratio $O(\log^4k)$ 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^2n)$ in time $n^{O(\log n)}$ and $O(n^ε)$ in time $n^{O(1/ε)}$, which, unlike ours, grow with $n$. On the hardness side, directed multicast stays $(1-ε)\ln k$-hard even when $\mathrm{OPT}=O(\log k)$, the regime in which the previous algorithms were weakest.