Plane Gossip: Approximating rumor spread in planar graphs∗
Jennifer Iglesias†1 , Rajmohan Rajaraman2 , R. Ravi1 , and Ravi Sundaram2

arXiv:1612.01492v2 [cs.DS] 14 Jul 2017

1

Carnegie Mellon University, Pittsburgh PA, USA, {jiglesia,ravi}@andrew.cmu.edu
2
Northeastern University, Boston MA, USA, {rraj,koods}@ccs.neu.edu
July 18, 2017

Abstract
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. Multi-commodity multicast models a classic information dissemination problem in
networks where the primary communication constraint 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 and the best approximation
√
e log n)
O(
, O(log n/ log log n), and O(log k/ log log k), respectively, where n is
factors known are 2
the number of nodes and k is the number of terminals in the multicast instance.
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 of the subgraph and the
maximum distance between any source-destination pair in the subgraph. We first show that for
any instance of the single-commodity 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 an instance with k terminals. This is the first upper bound on the integrality gap of the
natural LP; all previous algorithms, both combinatorial and LP-based, yielded approximations
with respect to the integer optimum. Using this integrality gap upper bound and shortestpath separators in planar graphs, we obtain our main result: an O(log3 k log n/(log log n))approximation for multi-commodity multicast for planar graphs, where k is the number of
source-destination pairs.
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 in a single step but only nodes with a single broadcasting neighbor get a non1
interfered message. In earlier work (Iglesias et al., FSTTCS 2015), we showed a strong Ω(n 2 −ǫ )hardness of approximation for computing a minimum gossip schedule in general graphs. Using
our techniques for the telephone model, we give an O(log2 n)-approximation for radio gossip in
planar graphs breaking this barrier. Moreover, this is the first bound for radio gossip given that
does not rely on the maximum degree of the graph.
Finally, we show that our techniques for planar graphs extend to graphs with excluded minors. We establish polylogarithmic-approximation algorithms for both multi-commodity multicast and radio gossip problems in minor-free graphs.
∗

This material is based upon research supported in part by the U. S. Office of Naval Research under award number
N00014-12-1-1001 and National Science Foundation under award number CCF-1527032.
†
Supported by the National Science Foundation Graduate Research Fellowship Program under Grant No.
2013170941.

1

Introduction

Rumor spreading in networks has been an active research area with questions ranging from finding
the minimum possible number of messages to spread gossip around the network [32, 3, 17] to
finding graphs with minimum number of edges that are able to spread rumors in the minimum
possible time in the network [16]. There is also considerable work in the distributed computing
literature on protocols for rumor spreading and gossip based on simple push and pull paradigms
(e.g., see [10, 19, 15, 11]).
The focus of this paper is the class of problems seeking to minimize the time to complete the
rumor spread, the prototypical example being the minimum broadcast time problem where
a message at a root node must be sent to all nodes via connections represented by an undirected
graph in the minimum number of rounds. Under the popular “telephone” model, every node can
participate in a telephone call with at most one other neighbor in each round to transmit the
message, and the goal is to minimize the number of rounds. This problem has seen active work in
designing approximation algorithms [21, 29, 4, 9]. One generalization of broadcast is the minimum
multicast time problem: We are given an undirected graph G(V, E) representing a telephone
network on V , where two adjacent nodes can place a telephone call to each other. We are given
a source vertex r and a set of terminals R ⊆ V . The source vertex has a message and it wants
to inform all the terminals of the message. To do this, the vertices of the graph can communicate
in rounds using the telephone model. The goal is to deliver the message to all terminals in the
minimum number of rounds.
Recently, a more general demand model called the multicommodity multicast was introduced
in [27]. In the minimum multicommodity multicast time problem, a graph G(V, E) is given
along with a set of pairs of nodes P = {(si , ti )|1 ≤ i ≤ k}, known as demand pairs. Each vertex
si has a message mi which needs be delivered to ti . The vertices communicate similar to the
multicast problem. The goal is to deliver the message from each source to its corresponding sink in
the minimum number of rounds. Note that there is no bound on the number of messages that can
be exchanged in a telephone call. In this sense, the telephone model captures a classic information
dissemination problem where the primary communication constraint is the number of connections
that a given node can make in each round, not link bandwidth.

1.1

Poly-logarithmic approximation for planar multicommodity multicast.

While even sub-logarithmic ratio approximations have been known for the minimum time multicast
problem
√ [21, 29, 4, 9], the best known approximation guarantees for the multicommodity case [27]
is Õ(2 log k ) where k is the number of different source-sink pairs.
Theorem 1.1. There is a polynomial time algorithm for minimum time multicommodity multicast
with k source-sink pairs in n-node undirected planar graphs that constructs a schedule of length
O(OP T log3 k logloglogn n ) where OP T is the length of the optimal schedule.
This result to extends in a natural way to bounded genus graphs. Our results make critical use
of the fact that planar graphs admit small-size balanced vertex separators that are a combination
of three shortest paths starting from any given node [31]. We aggregate messages at the paths,
move them along the path and then move them onto their destinations using a local multicast. To
break the overall multi-commodity multicast problem into recursive subproblems, we solve an LP
relaxation for the overall problem and for those pairs for which the LP uses the separator path
nodes in sending messages by a ”large” amount, we aggregate them to the separator paths and
move them along the paths. However, to define this aggregation automatically we need to use a
1

linear program which requires us to relate another lower bound for the schedule length that we
describe next.

1.2

Poise and a new LP rounding algorithm.

Suppose that the (single-commodity) multicast problem in a graph G with root r and terminals
R admits a multicast schedule of length L. Consider all the nodes I ⊆ V in the graph that are
informed of the message from the root in the course of the schedule. For every node v ∈ I consider
the edge through which v first heard the message and direct this edge into v. It is easy to verify
that this set of arcs forms an out-arborescence T rooted at r and spanning I. In particular, every
node in I except r has in-degree exactly one and there is a directed path from r to every vertex in
I.
Definition 1.2. Define the poise of an undirected tree T to be the sum of the diameter of the tree and
the maximum degree of any node in it. Define the poise of a directed tree to be that of its undirected
version (ignoring directions).
The discussion above of constructing a directed tree from a multicast schedule implies that the
poise of the tree constructed from a multicast schedule of length L is at most 3L (see also [29]).
The following lemma gives the relation in the other direction.
Lemma 1.3. [29] Given a tree on n nodes of poise L, there is a polynomial time algorithm to construct
a broadcast scheme of length O(L · logloglogn n ) from any root.
Note that a complete d-ary regular tree of depth d requires time d2 to finish multicast from
the root; If the size of the tree is n, then d = O( logloglogn n ). For this tree L = O( logloglogn n ) while any
broadcast scheme takes Ω(( logloglogn n )2 ) steps showing that the multiplicative factor is necessary.
Even though approximation algorithms for minimum poise trees connecting a root to a set of
terminals were known from earlier work [29, 9, 4], their guarantees are with respect to an optimal
(integral) solution and not any specific LP relaxation. In particular, the LP-based algorithm of [29]
rounds a solution to the poise LP in phases without preserving the relation of the residual LPs
that arise in the phases to the LP for the poise of the whole graph. Similarly, the LP-based
algorithm of [4] solves a series of LPs determining how to hierarchically pair terminals and form
the desired broadcast tree with cost within a logarithmic factor of the integral optimum poise,
but without relating the resulting tree to the LP value of the poise of the original graph. It
is not straightforward to use these methods to derive an integrality gap for the minimum poise
LP, and this has remained an open problem. Deriving an approximation algorithm for minimum
poise subgraphs for the single-commodity multicast version with a small integrality gap is a critical
ingredient in our approximation algorithm for multicommodity multicast problem in planar graphs
(Theorem 1.1). We derive the first such result.
Theorem 1.4. Given a fractional feasible solution of value L to a natural linear programming relaxation
of the minimum poise of a tree connecting a root r to terminals R (POISE-L LP, see Section 2), there
is a polynomial time algorithm to construct a tree spanning r ∪ R of poise O(L log k) where k = |R|
and n = |V |.
Our LP rounding for minimum poise are based on exploiting a connection to the theory of
multiflows [24, 5, 12]; this is an interesting technique in its own right that we hope will be useful
in obtaining other LP rounding results for connectivity structures while preserving degrees and
distances.
2

1.3

Radio Gossip in Planar Graphs.

Our techniques for addressing multicommodity multicast are also applicable to radio gossip in
planar graphs. In the radio model of communication that also occurs in rounds, a transmitting
node may broadcast to multiple nodes in around but a node may receive successfully in a given
time step only if exactly one of its neighbors transmits. The gossip problem is a special case of
the multicommodity multicast problem where the demand pairs include all possible pairs of nodes
(alternately, every node’s message must be transmitted to every other node). The minimum gossip
problem in the radio model has been widely studied [14] but all known upper bounds involve both
the diameter and degree of the network. In particular, for general n-node graphs, there is an
1
Ω(n 2 −ǫ )-hardness of approximation result for computing a minimum gossip schedule [18]. Our
next result breaks this barrier for planar graphs (the proof and algorithm are in Section 4).
Theorem 1.5. There is a polynomial time algorithm for minimum time radio gossip in an n-node
undirected planar graph that constructs a schedule of length O(OP T · log2 n) where OP T is the length
of the optimal gossip schedule.
Since radio broadcast from any node can already be achieved with additive poly-logarithmic
time overhead above the optimum [25], our algorithm for radio gossip focuses on gathering all the
messages to a single node. For this, we use the path-separator decomposition in planar graphs
to recursively decompose the graph and gather messages bottom up. However, the diameter of
subgraphs formed by the decomposition are not guaranteed to be bounded so we use a carefully
constructed degree-bounded matching subproblem to accomplish the recursive gathering: these
techniques adapt and extend the methods used for constructing telephone multicast schedules [27]
but apply them for the first time to the radio gathering case.

1.4

Minor-free Graphs

Both our results on planar graphs also naturally extend to minor-free graphs, as similar path
separator results are also known for minor-free graphs [1]. They are detailed in Section 5in the
Appendix for completeness.
Theorem 1.6. There is a polynomial time algorithm for minimum time multicommodity multicast with
k source-sink pairs in n-node undirected H-minor-free graph for a constant sized H that constructs a
schedule of length O(OP T log3 k logloglogn n ) where OP T is the length of the optimal schedule.
Theorem 1.7. There is a polynomial time algorithm for minimum time radio gossip in an n-node undirected H-minor-free graph for a constant sized H that constructs a schedule of length O(OP T log2 n)
where OP T is the length of the optimal gossip schedule.

1.5

Previous Work

Minimum time multicast in the telephone model. Finding optimal broadcast schedules
for trees was one of the first theoretical problems in this setting and was solved using dynamic
programming [28]. For general graphs, Kortsarz and Peleg [21] developed an additive approximation
√
algorithm which uses at most c · OP T + O( n) rounds for some constant c in an n-node graph.
They also present algorithms for graphs with small balanced vertex separators with approximation
ratio O(log n · S(n)) where S(n) is the size of the minimum balanced separator on graphs of
size n from the class. The first poly-logarithmic approximation for minimum broadcast time was
achieved by Ravi [29] and the current best known approximation ratio is O( logloglogn n ) due to Elkin
3

and Korsartz [9]. The best known lower bound on the approximation ratio for telephone broadcast
is 3 − ǫ [6].
In his study of the telephone broadcast problem, Ravi [29] introduced the idea of finding low
poise spanning trees to accomplish broadcast. In the course of deriving a poly-logarithmic approximation, Ravi also showed how a tree of poise P in an n-node graph can be used to complete
broadcast starting from any node in O(P · logloglogn n ) steps. His result provided an approximation
guarantee with respect to the optimal poise of a tree but not its natural LP relaxation that we
investigate.
Guha et al. [4] improved the approximation factor for multicasting in general graphs to O(log k)
where k is the number of terminals. The best known approximation factor for the multicast problem
is O( logloglogk k ) [9]. Both of [9, 4] present a recursive algorithm which reduces the total number of
uninformed terminals in each step of the recursion, while using O(OP T ) number of rounds in that
step. In [4], they reduce the number of uninformed terminals by a constant factor in each step and
so they obtain a O(log k)-approximation, but in [9], the number of uninformed terminals is reduced
by a factor of OP T which gives a O( logloglogk k )-approximation due to the fact that OP T = Ω(log k).
These papers also imply an approximation algorithm with factors O(log k) and O( logloglogk k ) for the
Steiner minimum poise subgraph problem; however, these guarantees are again with respect to the
optimum integral value for this problem and not any fractional relaxation.
For the multicommodity multicast problem, Nikzad √and Ravi [27] adapt the methods of [8, 9]
to present an algorithm with approximation ratio Õ(2 log k ) where k is the number of different
source-sink pairs. They also show that there is a poly-logarithmic approximation inter-reducibility
between the problem of finding a minimum multicommodity multicast schedule and that of finding
a subgraph of minimum generalized Steiner poise (i.e., a subgraph that connect all source-sink
pairs, but is not necessarily connected overall, and has minimum sum of maximum degree and
maximum distance in the subgraph between any source-sink pair).
Radio Gossip. The radio broadcast and gossip problems have been extensively studied (see
the work reviewed in the survey [13]). The best-known scheme for radio broadcast is by Kowalski
and Pelc [22] which completes in time O(D + log2 n), where n is the number of nodes, and D is
the diameter of the graph and is a lower bound to get the message across the graph from any
root. The O(log2 n) term is also unavoidable as demonstrated by Alon et al. [2] in an example with
constant diameter that takes Ω(log2 n) rounds for an optimal broadcast scheme to complete. Elkin
and Korsartz [7] also show that achieving a bound better than additive log-squared is not possible
unless N P ⊆ DT IM E(nlog log n ). For planar graphs, the best upper bound for radio broadcast
time is D + O(log n) given by [25]. The best bound for radio gossip known so far, however, is
O(D + ∆ log n) steps in an n-node graph with diameter D and maximum degree ∆ [14], even
though there is no relation in general between the optimum radio gossip time and the maximum
degree. Indeed, for general graphs, there is a polynomial inapproximability lower-bound for the
minimum time radio gossip problem [18].
Planar path separators. For our results on planar graphs, we rely on the structure of path√
separators. Lipton and Tarjan first found small O( n)-sized separators for n-node undirected
planar graphs [23]. More recently, planar separators based on any spanning tree of a planar graph
were found [31] with the following key property: these balanced vertex separators can be formed
by starting at any vertex and taking the union of three shortest paths from this vertex. Minor-free
graphs also admit small path-separators as found by [1]; in this case, the number of paths used
depends on the graphs which are excluded minors, but stays constant for constant-sized excluded
minors.

4

2

LP Rounding for Multicast in General Graphs

In this section we present an approximation algorithm for finding a minimum poise Steiner
subgraph, and establish an LP integrality gap upper bound, thus proving Theorem 1.4. We begin
by presenting a linear program for a multicommodity generalization of minimum poise Steiner
subgraph, which is useful for the multicommodity multicast problem. This linear program, when
specialized to the case where we need to connect a root r to a subset R of terminals, is our LP for
the minimum poise Steiner subgraph problem.

2.1

Linear Program for Poise

The generalized Steiner poise problem is to determine the existence of a subgraph containing paths
for every demand pair in K = {(si , ti )|1 ≤ i ≤ k} of poise at most L, i.e. every demand pair is
connected by a path of length at most L and every node in the subgraph has degree at most L.
We use indicator variables x(e) to denote the inclusion of edge e in the subgraph. Since the
poise is at most L, this is also an upper bound on the length of the path from any terminal to the
root. For every terminal (si , ti ) ∈ K, define Pi to be the set of all (simple) paths from si to ti .
We use a variable yt (P ) for each path P ∈ Pi that indicates whether this is the path used by si
to reach ti in the subgraph. For a path P , let ℓ(P ) denote the number of hops in P . The integer
linear program for finding a subgraph of minimum poise is given below.
minimize P
L = L1 + L2
subject to
x(e) ≤ L1
Pe∈δ(v)
y (P ) = 1
PP ∈P(t,r) t
ℓ(P )yt (P ) ≤ L2
PP ∈P(t,r)
P ∈P(t,r):e∈P yt (P ) ≤ x(e)
x(e) ∈ {0, 1}
yt (P ) ∈ {0, 1}

(P OISE − LP )
∀v ∈ V
∀t ∈ R
∀t ∈ R
∀e ∈ E, t ∈ R
∀e ∈ E
∀t ∈ R, P ∈ PL (t, r).

The first set of constraints specifies that the maximum degree of any node using the edges in
the subgraph is at most L1 . The second set insists that there is exactly one path chosen between
every pair (si , ti ) ∈ K. The third set ensures that the length of the path thus selected is at most
L2 . The fourth set requires that if the path P ∈ Pi is chosen to connect si to ti , all the edges in
the path must be included in the subgraph.
We will solve the LP obtained by relaxing the integrality constraints to nonnegativity constraints1 , and get an optimal solution x, y ≥ 0.
For the remainder of this section, we will focus on the rooted version of this problem. In
particular, there will be a root r and set of terminals R, then we will make K = {(r, t)|t ∈ R}. It
still remains to round a solution to POISE-LP to prove Theorem 1.4. Before presenting the rounding
algorithm in Section 2.3, we describe a result on multiflows that will be useful in decomposing our
LP solution into a set of paths that match terminals with each other.

2.2

Preliminaries

Given an undirected multigraph G with terminal set T ⊂ V of nodes, a multiflow is an edge-disjoint
collection of paths each of which start and end in two distinct terminals in T . The value of the
multiflow is the number of paths in the collection. Such a path between two distinct terminals is
1
Even though the number of path variables is exponential, it is not hard to convert this to a compact formulation
on the edge variables that can be solved in polynomial time. See e.g., [29]

5

called a T -path and a multiflow is called a T -path packing. For any terminal t ∈ T , let λ(t, T \ t)
denote the minimum cardinality of an edge cut separating t from T \ t in G. Note that in any
multiflow, the maximum number of paths with t as an endpoint is at most λ(t, T \ t). Furthermore,
since every path in a multiflow has to P
end in distinct vertices in T , the maximum value of any
λ(t,T \t)
, by summing over the maximum number of
multiflow for T is upper bounded by
t∈T
2
possible paths from each terminal and dividing by two to compensate for counting each path from
both sides. This upper bound can be achieved if a simple condition is met.
Theorem 2.1. [24, 5] If every vertex in V \ T has even degree, then there exists a multiflow for T of
P
\t)
.
value t∈T λ(t,T
2
The following simple construction will be useful in the rounding algorithm to identify good
paths to merge clusters. It is based off of a lemma from [29].
Lemma 2.2. Let G be a digraph where every node has at most one outgoing edge (and no self loops).
In polynomial time, one can find an edge-induced subgraph H of G such that H is a partition of the nodes
of G into a forest of directed trees each being an inward arborescence, and with |E(H)| ≥ |E(G)|/2.
Proof. Consider any connected component of G, if there are v vertices, then there are either v or
v − 1 edges (as each vertex has outdegree at most 1). If there are v edges, there is a cycle. When we
remove an edge from the cycle, we now have a connected component with v − 1 edges. If there are
v − 1 edges and all the vertices have outdegree at most 1, then it is already an inward arborescence.
An algorithm to find H would simply check the graph for directed cycles, and if any cycle exists,
it would remove an edge from that cycle. Any component which had a cycle has at least 2 edges,
and we remove at most 1 edge from every component. So, the resulting graph H has at least half
the edges that the original graph G had.

2.3

The Rounding Algorithm

The main idea of Algorithm 1 is to work in O(log k) phases, reducing the number of terminalcontaining components in the subgraph being built by a constant fraction at each stage [30]. We
begin with an empty tree containing only the terminals R, each in a cluster by themselves. In each
phase, we will merge a constant fraction of the clusters together carefully so that the diameter of
any cluster increases by at most an additive O(L) per phase: for this, we choose a terminal as a
center of each cluster. When we merge clusters, we partition the clusters into stars where we have
paths of length O(L) from the centers of the star leaf clusters to the center of the star center-cluster.
These steps closely follow those in [29]. The crux of the new analysis is to extract a set of stars
that merge a constant fraction of the current cluster centers using a solution to POISE-L LP.
The key subroutine to determine paths to merge centers is presented in Algorithm 2. This uses
the multiflow packing theorem of [24, 5].

2.4

Performance Ratio

In this section, we prove Theorem 1.4. The performance ratio of the rounding algorithm in the
theorem is a consequence of the following claims, the first of which follows directly from the path
pruning in Algorithm 2.
Lemma 2.3. The length of each path output by Merge-Centers(C ∗ ) is at most 4L.
Lemma 2.4. The expected number of paths output by Merge-Centers(C ∗ ) is Ω(|C ∗ |).
6

Algorithm 1 LP Rounding for Poise-L tree
1: Clusters C ← R; Centers C ∗ ← R; Solution graph H ← ∅; Iteration i ← 1.
2: while |C| > 1 do
3:
Use Algorithm Merge-Centers(C ∗ ) to identify a subgraph Fi whose addition reduce the number of clusters by a constant fraction;
4:
H ← H ∪ Fi ; Update C to be the set of clusters after adding the subgraph Fi , and update
C ∗ to be the centers of the updated clusters based on the star structure from Algorithm
Merge-Centers(C ∗ ). Increment i.
5: end while
6: Add a path of length at most L from r to the center of the final cluster in H. Find a shortest
path tree in H rooted at r reaching all the terminals in R and output it.
Proof. The main observation here is that the total number of edges in the multigraph G is at
most |C ∗ | · L · M . To see this, note that each terminal t retains its flow of value 1 in POISE-LP
corresponding to the paths with nonzero value for yt . Thus in the scaled version, it retains M
paths to the root, and the average number of hops in these paths is at most L2 ≤ L hops, for each
terminal. Summing over all terminals, the number of edges in G is at most |C ∗ | · L · M .
∗
The total number of paths discarded cannot exceed |C 4|·M . Otherwise the paths each of length
at least 4L each would need more edges
in G than
we started with. After discarding, we expect to
|C ∗ |·M
3|C ∗ |
1
∗
still collect at least M · (|C | · M − 4 ) = 4 paths fractionally. Hence the expected number of
∗
terminals in the subgraph H is at least 3|C4 | . The set of arcs finally retained in H ′′ is at least one
third of the
nodes of H, the worst case being a path of two arcs. This leads to an expectation of
|C ∗ |
at least 4 paths finally output to merge the initial clusters.
Lemma 2.5. The distance of any node in a cluster to its center increases by at most 4L in the newly
formed cluster by merging paths corresponding to stars in H ′′ . Thus, the diameter of any cluster in
iteration i is at most 8iL.
Proof. The proof is by induction over i, and is immediate by observing that any node can reach
the new merged cluster center say c by first following the path to its old center, say t and then
following the path Pt corresponding to the arc in H ′′ from t to c. By Lemma 2.3 above, the length
of Pt is at most 4L and the claim follows.
Lemma 2.6. The maximum degree at any node of G induced by the union of paths output by MergeCenters(C ∗ ) is O(L).
Proof. This is a simple consequence of the performance guarantee of rounding the LP solution
obtained for the collection of paths. Since the paths we found pack into the LP solution 2x (from
the property of the multiflow packing), the expected congestion due to the chosen random paths
on any edge e is at most 2x(e). From the first constraint in the LP, the expected congestion at any
node due to paths incident on it is at most 2L1 ≤ 2L, by linearity of expectation.
We apply the classic rounding algorithm of [20]. Since the length of each path in the collection
is at most 4L and the expected congestion is at most 2L, we obtain that there is a rounding, which
can be determined in polynomial time, such that the node congestion (degree) in the rounded
solution of at most 4L. 4L.
By Lemma 2.4, the number of iterations of the main Algorithm 1 is O(log k) where k is the
number of terminals. Lemma 2.5 guarantees that the subgraph of the final cluster containing all the
7

Algorithm 2 Merge-Centers(C ∗ ) using LP solution x
1: Multiply the POISE-LP solution x by the least common multiple M of the denominators in
the nonzero values of x to get a multigraph.
2: For every terminal t ∈ C ∗ , retain the edges in the paths corresponding to the paths in its LPsolution with nonzero value (i.e., paths P with nonzero yt (P )), for a total of M connectivity
from t to r. Note that the union of all the retained edges gives connectivity M from every
t ∈ C ∗ to r and hence by transitivity, between each other.
3: Double each edge in the multigraph and use Theorem 2.1 to find a multiflow of value
P
P
λ(t,C ∗ \t)
∗
∗
≥ t∈C ∗ 2M
t∈C ∗
2
2 = |C | · M . Note that each terminal in C has at least M paths in
the multiflow.
4: Eliminate all the paths in the multiflow of length longer than 4L.
5: For every terminal t, pick one of the M paths incident on it uniformly at random and set this
path to be Pt . If the chosen path is eliminated due to the length restriction, set Pt ← ∅.
6: Let H be an auxiliary graph on vertex set C ∗ with at most one arc coming out of each t ∈ C ∗
pointing to the other endpoint of Pt (or add no edge if Pt = ∅).
7: Apply Lemma 2.2 to the subgraph of H made of nodes, to get a collection H ′ of in-trees. For
each in-tree, partition the arcs into those in odd and even levels of the tree and pick the set
with the larger number of arcs. Note that these sets form stars originating from a set of centers
and going to a single center. Let H ′′ denote the set of these stars.
8: For each arc of the stars in H ′′ , include the path Pt originating at the leaf of the star corresponding to the arc in H ′′ , and output the collection of paths.
terminals has distance O(log k ·L) between any pair of terminals. Since the final output is a shortest
path tree of this subgraph rooted at r, its diameter is also of the same order. Lemma 2.6 ensures
that the total degree of any node in the subgraph of the final cluster is O(log k · L), and this is also
true for the tree finally output. This completes the proof of Theorem 1.4. We can derandomize the
above randomized algorithm using the standard method of pessimistic estimators [26].

3

Approximating multicommodity multicast on planar graphs

In this section we prove Theorem 1.1. Let G = (V, E) be the given planar graph, with n = |V |, and
let K = {(si , ti ) : 1 ≤ i ≤ k} be the set of the k source-destination pairs that need to be connected.
Let γ = 1/ log k. We given a brief overview of our algorithm PlanarMCMulticast, which is fully
described in Algorithm 3.
PlanarMCMulticast is a recursive algorithm, breaking the original problem into smaller problems each with at most a constant fraction of the demand pairs in K in each recursive call, thus
having O(log k) depth in the recursion. For a given graph, the algorithm proceeds as follows.
• Find a node separator composed of three shortest paths from an arbitrary vertex [31] to break
the graph into pieces each with a constant fraction of the original nodes.
• Solve a generalized Steiner poise LP on the given pairs to identify demand pairs that cross
the separator nodes to an extent at least Ω(γ).
• Satisfy these demand pairs by routing their messages from the sources to the separator,
moving the messages along the separator (since they are shortest paths, so this movement
takes minimal time) and back to the destinations, by scaling the LP values by a factor of
O( γ1 ) and using Theorem 1.4 to find a low poise tree to route to/from the separator.
8

• For the remaining demand pairs (which are mainly routed within the components after removing the separators), PlanarMCMulticast recurses on the pieces.
The key aspect of planarity that is used here is the structure theorem that planar graphs contain
[31] small-size balanced vertex separators that are a combination of three shortest paths starting
from any given node.
Algorithm 3 PlanarMCMulticast(G, K)
1: Base case: When K = {(s1 , t1 )} has one demand pair, schedule the message on the shortest
path between the source, s1 , and destination, t1 .
2: Separate the graph: Define the weight of a node as the number of source-destination pairs
it is part of, and the weight of a subset of nodes as the sum of their weights. Find a 3-path
separator P of G, given by shortest paths P1 , P2 , and P3 , whose removal partitions the graph
into connected components each of which has weight at most half that of the graph [31].
3: Partition the terminal pairs: Partition the set K into two subsets, by solving the POISE-LP.
• Let K1 consist of pairs (si , ti ) such that in POISE-LP, the fraction of the unit flow from si
to ti that intersects P is at least γ.

• Let K2 = K − K1 consist of the remaining pairs, i.e. pairs (si , ti ) such that in the LP, the
fraction of the unit flow from si to ti that intersects P is less than γ

4:

5:

6:

7:

8:

9:

Scale flow for pairs in K1 : For each pair (si , ti ) in K1 , scale the flow between si and ti in
the POISE-LP by γ3 so there exists a path Pj which intersects a unit of this scaled si -ti flow;
remove other si -ti flows that does not intersect Pj up to a unit. Assign (si , ti ) to a set Sj .
Create 3 minimum poise Steiner tree problems for K1 : For each path Pj , create a
minimum Steiner poise problem as follows: (i) attach, to the graph, an auxiliary binary tree
Tj with nodes of Pj forming the leaves, and adding new dummy internal nodes (This step is
similar to [27]); (ii) set the root of the binary tree to be the root for the Steiner poise problem,
and the terminals to be all the si and ti in Sj .
Round the POISE-LP solution: For each Pj , round the LP to obtain a Steiner tree Tj of
small poise connecting all the terminals in Sj with the root using the algorithm from Theorem 1.4.
Construct schedule for K1 : Use Lemma 1.3 on the tree Tj to perform a multicast between
all terminals in it as follows: use the multicast schedule to move the messages, from the sources,
till they hit the path Pj , then move messages along the path followed by the multicast schedule
in reverse to move them towards the destinations. (Moving messages along a path can be
achieved by a schedule that alternates between the even and odd matchings in the path for as
many steps as the target length of the schedule)
Scale flow for K2 : For each pair (si , ti ) in K2 , remove any flow that intersects P and scale the
1
) so as to continue to have unit total flow between
remaining flow (by a factor of at most 1−γ
the pair.
Recurse for K2 : For each connected component Cj , let K2j denote the subset of K2 with both
terminals in Cj . Run PlanarMCMulticast(Cj , K2j ) in parallel.

We now prove that PlanarMCMulticast constructs, in polynomial-time, a multicommodity multicast schedule a schedule of length O((OP T log3 k · logloglogn n ) where OP T is the length of the optimal
schedule.
1. Observe that 3OP T is an upper bound for the value L for the POISE-LP for this instance.
9

2. In Step 2 of PlanarMCMulticast, the separator is obtained using the algorithm in [31]. In
Step 3, we use POISE-LP, as specified in Section 2 to find the fractional solution. In Step
4 of PlanarMCMulticast, unit si − ti flow is achieved by scaling up the LP cost by at most
a factor of 3/γ since at least γ/3 flow intersects one of the three paths in P. Now, observe
that this scaled LP solution immediately yields a valid solution to POISE-LP in Step 5.
Applying Theorem 1.4, in Step 6, with the value of L = O(OP T log k) gives a tree of poise
O(OP T log2 k).
3. The algorithm performs O(log k) (recursive) phases; the poise of the tree at the ith level of
1
(in Step 8)
recursion is itself based on an LP that has been scaled by a factor of at most 1−γ
3
in the previous i − 1 = O(log k) iterations followed by a final scaling of γ in the last iteration.
In any iteration, the total factor by which the initial LP value of OP T is scaled is at most
1
1 i−1 3
)
· γ ≤ (1 + γ) γ · γ3 = O(log k) since γ = log1 k .
( 1−γ
4. In Step 7, we incur a multiplicative factor of O( logloglogn n ) in going from a small poise tree to
a schedule. Here, we crucially use the fact that the separator paths are shortest paths - for
a demand pair (si , ti ) let fi denote the first vertex on the separator path that the message
arrives at after leaving source si and let li denote the last vertex (on the separator path) that
the message departs from, on its way to the destination ti ; then fi and li must be at most an
additive O(OP T ) of the sum of the lengths of the paths from si to fi and li to ti along the
separator path, since every demand pair has a path of length O(OP T ) between them in the
LP solution in this subgraph. Thus in Step 7, we can wait to aggregate all messages from the
sources at the separator path, then move all the messages one way along the path and then
the opposite way, for as many time steps as the poise of the integral tree, without more than
tripling the total schedule.
5. Since there are O(log k) recursive phases, the final schedule has length
O(OP T log3 k logloglogn n ).
This proves Theorem 1.1.

4

A polylogarithmic approximation for radio gossip on planar
graphs

In this section, we present an O(log2 n)-approximation algorithm for finding a radio gossip schedule
on planar graphs, and prove Theorem 1.5.
Let G = (V, E) be a given planar graph. Once the messages from all nodes have all been
gathered together at a node we can easily broadcast them back out in O(OP T + log2 n) rounds
using [22]. So we focus on gathering the messages together at one node. To do this, we recursively
find 3-path separators in the graph [31] to decompose it into connected components. Then, working
backwards, we gather messages from the 3-path separators found in an iteration at the nodes of
the 3-path separators found in previous iterations, using techniques from telephone multicast [27].
The key properties used in the recursive algorithm are that the number of paths in the separator is
a constant 3 and the paths are all shortest paths in the component they separate from some vertex.
We assume the optimal schedule has length L. Note that L ≤ 2n since gossip can be achieved
by simply choosing any spanning tree and broadcasting one node at a time in post-order (to gather
all messages at the root) and then in reverse post-order (to spread all messages back to all nodes).

10

Algorithm 4 A gathering procedure for radio gossip in planar graphs.
1: Clusters C0 ← {V }; Vertices V0 ← V ; Graph G0 ← G; Iteration i ← 1.
2: while Vi−1 6= ∅ do
3:
for all connected component C ∈ Ci−1 do
4:
Choose some v ∈ C. Find shortest paths p1 , p2 , p3 from v that form a 3-path separator in
C using [31]; Add these to Pi , the paths found in the ith iteration.
5:
Add v and every (2L + 1)st vertex along paths p1 , p2 , p3 to Ni
6:
end for
7:
Remove the vertices in Pi from Vi−1 to get Vi ; Let Gi be G[Vi ] and Ci denote the connected
components of Gi ; Increment i.
8: end while
9: while i > 0 do
10:
Do 2L rounds of radio broadcasts in series on nodes that are 2L + 1 apart from each other
along the paths in Pi to gather all the messages on Pi at the nodes Ni .
i−1
11:
Form G′i a bipartite graph from Ni to Ui = ∪j=1
Pj . Add an edge uv ∈ Ei′ if there is a path
from u ∈ Ni to v in G[Ci−1 ∪ {v}] of length at most L. Find a 3L-matching in G′ where every
vertex of Ui has degree at most 3L.
12:
Do up to L rounds of radio broadcast to get the messages from Ni to within one node of Ui ,
along the paths in the 3L-matching found above. Note that the messages stay within the
component in Ci−1 containing u for this part.
13:
Move the messages from the last nodes in Ci−1 to their destination nodes in Ui in the 3Lmatching using at most 9L rounds for each of the paths (27L log n total).
14:
Decrement i
15: end while
We also assume that L > 2 ( L ≤ 2 only occurs if there are 1 or 2 nodes total). The details of the
algorithm are given in Algorithm 4.
We will first prove a couple lemmas needed for the proof of Theorem 1.5.
Lemma 4.1. The graph G′i has a 3L matching which matches ever vertex of Ni to a some vertex of
Ui and every vertex of Ui has degree at most 3L.
Proof. Consider the graph G′i = (Ni , Ui , Ei′ ). Let pv be a path that v’s message take from v to r in
the optimal solution. Let p′v be the prefix of pv until the first vertex of Ui . All the paths pv have
length at most L (since this is the length of the optimal schedule). For each node w ∈ Vi , w is in
at most one of the p′v for v ∈ Ni . This is because if two p′v ’s from the same path in Pi arrive at
a node, there would be a path of length at most 2L between two nodes in Ni from the same path
Pi ; But the paths in Pi were chosen to be shortest paths in Ci−1 , and Ni were nodes that were
pairwise distance 2L + 1 from each other, a contradiction. Now consider u ∈ Ui and the p′v for Ni
that match to u: there can be at most L nodes from which messages go from Vi to u (since that
is an upper bound on its message receiving degree in the optimal solution). Thus, in the optimal
solution there are at most 3L paths from Ni to any specific node in Ui and these paths have length
at most L. So, there must exist a 3L-matching in G′ which matches every vertex of Ni to some
vertex of Ui and no vertex of Ui has degree more than 3L.
Lemma 4.2. Each iteration of the step 13 in algorithm 4 takes time at most O(L log n) and moves
the messages to Ui .
11

Proof. In Algorithm 4, step 13 is just to achieve the last step of message movement in the qv paths.
Each node w ∈ Vi can be adjacent to at most 3 nodes in a given path of Pj for any j < i, as these
paths are shortest paths in Gj−1 , and in particular these nodes are within 2 of each other in the
path. Also, for a given w ∈ Vi , w can be adjacent to multiple paths in Pj but they must all be in
the same component of Cj−1 , and there is at most three such paths. Let Sjk (ℓ) be every third vertex
on the paths Pjk starting with the ℓth vertex. In 3L steps (the maximum degree of the matching at
these nodes) we can gather the messages that need to be received at Sjk (ℓ) as no node is adjacent
to two nodes in this set. Doing this gathering for every shift ℓ from one to three, and each of three
choice of which path k, a total of 27L steps gets the message from the qv to Pj . This process is
repeated for each collection Pj with j < i. Now all the messages that were along Pi have been
moved to some node in Ui = ∪i−1
j=1 Pj in 27L log n steps.
Having established the lemmas, we now give the proof of Theorem 1.5.
Proof of Theorem 1.5. First, we establish that the algorithm runs correctly. Let r be the root
(chosen in the first iteration). First the algorithm gathers the messages on the Pi to Ni . We will
divide the paths into Pi1 , Pi2 , Pi3 , so that each component of Ci−1 that has three paths puts one
path in each of these sets. Now, we will handle each of the Pij one at a time. To deal with Pij , in
the kth step, the nodes which are 2L − k further from a node in Ni broadcast all their messages
to the node one closer to Ni . There is no interference amongst the nodes in Vi−1 as only nodes at
distance at least 2L in each component of Ci−1 are broadcasting at a time, and nodes in different
components are non-adjacent (since they are disconnected by the separators Pi−1 ). This will gather
all the messages along Pij . Doing this once for each of the Pij in 2L steps, all the messages currently
on Pi will be gathered at the Ni in 6L steps. The messages are all currently at Ni or Ui .
Lemma 4.1 tells us that G′i has a 3L-matching as desired, and so we can find such a matching.
Once a matching is chosen, let qv be a shortest path within Gi−1 from v ∈ Ni to the vertex it is
matched with in Ui . Within each component of Ci , we can broadcast along the qv for every Ni
in one of the paths simultaneously; There will be no interference as the Ni ’s and their matching
paths are far apart within Ci−1 . Thus, it takes at most L rounds of radio broadcasting to move the
messages from Ni along their qv to the vertex before Ui .
Lemma 4.2 gives us that in time O(L log n) we move the messages onto Ui .
In the last iteration of the process, we will have all the messages on the first path separator P1 .
P1 is a path separator of shortest paths on the whole graph and the diameter of G is a lower bound
on L. So, in 3L steps we can move the messages from P1 to r. We have now successfully gathered
all the messages to r.
The time it takes to deliver all the messages to r is at most O(L log2 n). The path separator
ensures that each component has at most a constant fraction of the number of vertices of the
original graph. Therefore, the final i ≤ log n. Each iteration, the number of rounds of broadcast
we do is 6L in the first part and 27L log n in the last step. So, this schedule uses O(L log2 n) steps
to gather all the messages at r.

5

Minor-free graphs

In this section, we prove that both results on planar graphs can be extended to any family of minorfree graphs. For this section, we will have to use the more general definition for path-separators.

12

Definition 5.1. [1] A vertex-weighted graph G is k-path separable if there exists a subgraph S, called
a k-path separator, such that:
1. S = P0 ∪ P1 ∪ . . . where each subgraph Pi is the union of ki shortest paths in G\ ∪j<i Pj
P
2.
i ki ≤ k
3. either G\S is empty, or each connected component of G\S is k-path separable and has total
vertex weight at most half of the original.
This definition of path separator while more complicated can be integrated into our PlanarMCMulticast algorithm and algorithm 4 with only small adjustments. We will use the following to
theorem which tells us when a k-path separator exists and can be found.
Theorem 5.2. [1] Every H-minor-free weighed connected graph is k(H)-path separable, and a k(H)path separator can be computed in polynomial time.
Note that k(H) = O(|H|) in the above construction.

5.1

Multicommodity multicast in minor-free graphs

Consider that our graph is H-minor free and k(H) is the number of paths needed for the path
separator. We will need to repeat steps 3-8 of the original algorithm for each subgraph of shortest
paths. Other than that, the algorithm remains the same.
The main changes to the algorithm are as follows.
• The path separator we find is different.
• We may need to iterate through steps 3-8 of the original algorithm multiple times.
Since these are the only changes to the algorithm, we first see that finding the path separator
takes polynomial time, and the number of iterations increases by at most a factor of k(H) (a
constant) so the algorithm still runs in polynomial time.
The only other change to the analysis is that the number of recursions is k(H) log k. This gives
1
1 k(H)γ 3
)
that we incur a factor of ( 1−γ
γ when scaling the LP. Since γ = log k , the LP gets scaled
by a factor of O(ek(H) log k). Since |H| and hence k(H) is a constant, we get that the resulting
schedule from this algorithm is at most O((OP T log k + log n) log2 k logloglogn n ). In terms of k(H), our
algorithm builds a schedule that takes O((OP T log k + log n) log2 k logloglogn n k(H)ek(H) )
This proves theorem 1.6.

5.2

Radio Gossip in Minor-free Graphs

The modification to go from radio gossip on planar graphs to radio gossip on minor-free graphs is
even more simple. Let k = k(H) where our graph G is H-minor-free. We only change how we set
up all of our initial sets; Pi , Ci , Vi , Ni , Ui . For each iteration, we will define up to k of these sets
one for each of the (potential) subgraphs which compose the path separator.
The only major change to this algorithm is the set-up. In the set-up, we have to process the
subgraphs which compose the path separator one at a time (as opposed to there only being one
subgraph which is the whole path separator). This only increases the number of iterations by a
factor a k(H).
The other change is that everywhere we had a 3 before it now becomes a k = k(H). All our
previous lemmas and theorems hold if we change the 3 arising from the planar case to k. Therefore,
13

we have shown that this algorithm produces a schedule for gathering which runs in time O(L log2 n)
(or O(Lk 3 log2 n) if k is not constant) to gather all the messages in one place.
We again use the result of Kowalski and Pelc to broadcast the messages once they have been
gathered [22]. This broadcast takes time L + O(log2 n), so the whole gossip schedule takes time
O(L log2 ) proving Theorem 1.7 as desired. We again use the result of Kowalski and Pelc to broadcast
the messages once they have been gathered [22]. This broadcast takes time L + O(log2 n), so the
whole gossip schedule takes time O(L log2 n) proving Theorem 1.7 as desired. If we don’t assume
k = k(H) is a constant, then the algorithm takes time O(Lk 3 log2 n).

References
[1] I. Abraham and C. Gavoille. Object location using path separators. In PODC, pages 188–197,
2006.
[2] N. Alon, A. Bar-Noy, N. Linial, and D. Peleg. A lower bound for radio broadcast. J. Comput.
Syst. Sci., 43:290–298, 1991.
[3] B. Baker and R. Shostak. Gossips and telephones. Discrete Mathematics, 2(3):191–193, 1972.
[4] A. Bar-Noy, S. Guha, J. Naor, and B. Schieber. Message multicasting in heterogeneous networks. SIAM J. Comput., 30(2):347–358, 2000.
[5] B. Cherkassky. Mnogopolyusnye dvukhproduktovye zadachi [russian: Multiterminal two commodity problems]. Issledovaniya po Diskretnoi Optimizatsii [Russian: Studies in discrete optimization], pages 261–289, 1976.
[6] M. Elkin and G. Kortsarz. A combinatorial logarithmic approximation algorithm for the
directed telephone broadcast problem. SIAM J. Comput., 35(3):672–689, 2005.
[7] M. Elkin and G. Kortsarz. Polylogarithmic additive inapproximability of the radio broadcast
problem. SIAM J. Discrete Math, 19(4):881–899, 2005.
[8] M. Elkin and G. Kortsarz. An approximation algorithm for the directed telephone multicast
problem. Algorithmica, 45(4):569–583, 2006.
[9] M. Elkin and G. Kortsarz. Sublogarithmic approximation for telephone multicast. J. Comput.
Syst. Sci., 72(4):648–659, 2006.
[10] U. Feige, D. Peleg, P. Raghavan, and E. Upfal. Randomized broadcast in networks. Random
Structures & Algorithms, pages 447–460, 1990.
[11] N. Fountoulakis, K. Panagiotou, and T. Sauerwald. Ultra-fast rumor spreading in social
networks. In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete
Algorithms, SODA ’12, pages 1642–1660. SIAM, 2012.
[12] A. Frank. Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics
and Its Applications. OUP Oxford, 2011.
[13] L. Gasieniec. On efficient gossiping in radio networks. In S. Kutten and J. erovnik, editors, Structural Information and Communication Complexity, volume 5869 of Lecture Notes in
Computer Science, pages 2–14. Springer Berlin Heidelberg, 2010.

14

[14] L. Gasieniec, D. Peleg, and Q. Xin. Faster communication in known topology radio networks.
Distributed Computing, 19(4):289–300, 2007.
[15] G. Giakkoupis. Tight bounds for rumor spreading in graphs of a given conductance. In
T. Schwentick and C. Dürr, editors, 28th International Symposium on Theoretical Aspects of
Computer Science (STACS 2011), volume 9 of Leibniz International Proceedings in Informatics (LIPIcs), pages 57–68, Dagstuhl, Germany, 2011. Schloss Dagstuhl–Leibniz-Zentrum fuer
Informatik.
[16] M. Grigni and D. Peleg. Tight bounds on minimum broadcast networks. SIAM J. Discrete
Math., 4(2):207–222, 1991.
[17] A. Hajnal, E. C. Milner, and E. Szemerédi. A cure for the telephone disease. Canad. Math.
Bull, 15(3):447–450, 1972.
[18] J. Iglesias, R. Rajaraman, R. Ravi, and R. Sundaram. Rumors across radio, wireless, telephone.
In FSTTCS, pages 517–528, 2015.
[19] R. Karp, C. Schindelhauer, S. Shenker, and B. Vocking. Randomized rumor spreading. In
Proceedings of the 41st Annual Symposium on Foundations of Computer Science, FOCS ’00,
pages 565–, Washington, DC, USA, 2000. IEEE Computer Society.
[20] R. M. Karp, F. T. Leighton, R. L. Rivest, C. D. Thompson, U. V. Vazirani, and V. V. Vazirani.
Global wire routing in two-dimensional arrays. Algorithmica, 2(1):113–129, Nov 1987.
[21] G. Kortsarz and D. Peleg. Approximation algorithms for minimum-time broadcast. SIAM J.
Discrete Math., 8(3):401–427, 1995.
[22] D. R. Kowalski and A. Pelc. Optimal deterministic broadcasting in known topology radio
networks. Distributed Computing, 19(3):185–195, 2007.
[23] R. J. Lipton and R. E. Tarjan. A separator theorem for planar graphs. SIAM J. Applied
Mathematics, 36(2):177–189, 1979.
[24] L. Lovász. On some connectivity properties of eulerian graphs. Acta Mathematica Academiae
Scientarum Hungaricae, 28:129–138, 1976.
[25] F. Manne, S. Wang, and Q. Xin. Faster radio broadcast in planar graphs. In WONS, pages
9–13, 2008.
[26] R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge International Series on
Parallel Computation. Cambridge University Press, 1995.
[27] A. Nikzad and R. Ravi. Sending secrets swiftly: Approximation algorithms for generalized
multicast problems. In Automata, Languages, and Programming, pages 568–607. Springer,
2014.
[28] A. Proskurowski. Minimum broadcast trees. IEEE Trans. Computers, 30(5):363–366, 1981.
[29] R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time. In FOCS,
pages 202–213. IEEE, 1994.
[30] R. Ravi. Matching based augmentations for approximating connectivity problems. In LATIN,
pages 13–24. Springer, 2006.
15

[31] M. Thorup. Compact oracles for reachability and approximate distances in planar digraphs.
J. ACM, 51(6):993–1024, 2004.
[32] R. Tijdeman. On a telephone problem. Nieuw Archief voor Wiskunde, 3(19):188–192, 1971.

16

