Plane Gossip: Approximating Rumor Spread in Planar Graphs

We study the design of schedules for multi-commodity multicast. In this problem, we are given an undirected graph G and a collection of source-destination pairs, and the goal is to schedule a minimum-length sequence of matchings that connects every source with its respective destination. The primary communication constraint of the multi-commodity multicast model is the number of connections that a given node can make, not link bandwidth. Multi-commodity multicast and its special cases, (single-commodity) broadcast and multicast, are all NP-complete. Multi-commodity multicast is closely related to the problem of finding a subgraph of optimal poise, where the poise is defined as the sum of the maximum degree and the maximum distance between any source-destination pair. We show that for any instance of the multicast problem, the minimum poise subgraph can be approximated to within a factor of \(O(\log k)\) with respect to the value of a natural LP relaxation in a graph with k source-destination pairs. This is the first upper bound on the integrality gap of the natural LP; all previous algorithms yielded approximations with respect to the integer optimum. Using this integrality gap upper bound and shortest-path separators in planar graphs, we obtain our main result: an \(O(\log ^3 k \frac{\log n}{\log \log n})\)-approximation for multi-commodity multicast for planar graphs which improves on the \(2^{\widetilde{O}(\sqrt{\log n})}\)-approximation for general graphs.

We also study the minimum-time radio gossip problem in planar graphs where a message from each node must be transmitted to all other nodes under a model where nodes can broadcast to all neighbors and only nodes with a single broadcasting neighbor get a non-interfered message. In earlier work Iglesias et al. (FSTTCS 2015), we showed a strong \(\varOmega (n^{\frac{1}{2} - \epsilon })\)-hardness of approximation for computing a minimum gossip schedule in general graphs. Using our techniques for the telephone model, we give an \(O(\log ^2 n)\)-approximation for radio gossip in planar graphs breaking this barrier. Moreover, this is the first bound for radio gossip given that doesn’t rely on the maximum degree of the graph.