Broadcasting in processor networks means disseminating a single piece
of information, which is originally known only at some nodes, to all m
embers of the network. The goal is to inform everybody using as few ro
unds as possible, that is minimize the broadcast time. Given a graph a
nd a subset of nodes, the sources, the problem to determine its specif
ic broadcast time, or more generally to find a broadcast schedule of m
inimal length has been shown to be NP-hard. In contrast to other optim
ization problems for graphs, like vertex cover or traveling salesman,
little was known about restricted graph classes for which polynomial t
ime algorithms exist, for example for graphs of bounded treewidth. The
broadcasting problem is harder in this respect because it does not ha
ve the finite-state property. Here, we will investigate this problem i
n detail and prove that it remains hard even if one restricts to plana
r graphs of bounded degree or constant broadcasting time. A simple con
sequence is that the minimal broadcasting time cannot even be approxim
ated with an error less than 1/8, unless P = NP. On the other hand, we
will investigate for which classes of graphs this problem can be solv
ed efficiently and show that broadcasting and even a more general vers
ion of this problem becomes easy for graphs with good decomposition pr
operties. The solution strategy can efficiently be parallelized, too.
Combining the negative and the positive results reveals the parameters
that make broadcasting difficult. Depending on simple graph propertie
s the complexity jumps from NC or P to NP. (C) 1998 Elsevier Science B
.V. All rights reserved.