# Deformed spaces and loop cosmology

Marco Valerio Battisti  ICRA and Phys. Dept. University of Rome “Sapienza”,
P.le A. Moro 5 00185 Rome, Italy<EMAIL_ADDRESS>
###### Abstract

The non-singular bouncing solution of loop quantum cosmology is reproduced by
a deformed minisuperspace Heisenberg algebra. This algebra is a realization of
the Snyder space, is almost unique and is related to the $\kappa$-Poincaré
one. Since the sign of the deformation parameter it is not fixed, the
Friedmann equation of braneworlds theory can also be obtained. Moreover, the
sign is the only freedom in the picture and these frameworks are the only ones
which can be reproduced by our deformed scheme. A generalized uncertainty
principle for loop quantum cosmology is also proposed.

## Introduction

In the last years a wide interest in the analysis of the non-commutative
framework is increased (for a review see [1]). In particular, this approach
can be considered a plausible candidate for describing physics at the Planck
scale [2] and can be related to the intuitions of doubly special relativity
(DSR) [3] which arises as a semi-classical limit of quantum gravity (see [4]
and the references therein). On the other hand, a prerequisite of any quantum
theory of gravity is to solve the space-time singularities predicted by the
Einstein theory of general relativity. One of the most important example is
the big-bang singularity appearing in the standard model of cosmology, which
Friedmann dynamics is expected to be modified by quantum effects in the regime
of small scale factor. Loop quantum cosmology (LQC) [5] leads to a resolution
of the singularity replacing the big-bang by a big-bounce as soon as the
matter energy density reaches the Planck scale, i.e. in this extreme region
(quantum) gravity behaves repulsively [6].

From this perspective it is natural to investigate the fate of the
cosmological singularity in a deformed (minisuper)-space framework [7]. Here,
we consider generalized commutation relations which leave undeformed the
translation group and preserve the rotational invariance, and apply this
framework to the Friedmann-Robertson-Walker (FRW) Universes (for more details
see [8]). As a result the effective Friedmann equation of LQC [9] naturally
arises from the deformed scheme. Interesting, since the deformed Heisenberg
algebra is fixed up to a sign, also the braneworlds Friedmann equation [10] is
predicted by our model. In other words, this deformed phase space can be
regarded, from a phenomenological point of view, as an effective framework
which is able to describe the results obtained in both LQC and Randall-Sundrum
braneworlds scenario. In this deformed scheme, the different predictions of
such theories can be easily understood considering the opposite sign in the
deformation term. It is worth noting that, a generalized uncertainty principle
naturally arises in our framework and, in the braneworlds-like case, it
resembles the one predicted by string theory. At the same level, a generalized
uncertainty relation can also be proposed for LQC.

The paper is organized as follows. Section 1 is devoted to discuss a non-
commutative space and its commutations relations. In Section 2 this framework
is applied to the isotropic cosmological models analyzing the modifications
induced on the Friedmann equation. Finally, in Section 3, implications of the
picture are analyzed. Concluding remarks follow.

##  1 Deformed Heisenberg algebra

Let us start by considering a $n$-dimensional deformed (non-commutative)
Euclidean space such that commutator between the coordinates has the non-
trivial structure

$[\tilde{x}_{i},\tilde{x}_{j}]=\mp i\alpha M_{ij},$ (1)

where with $\tilde{x}$ we refer to the non-commutative coordinates and
$\alpha>0$ is the deformation parameter with dimension of a length square. We
then demand that the rotation generators $M_{ij}=x_{i}p_{j}-x_{j}p_{i}$
satisfy the ordinary $SO(n)$ algebra and that the translation group is not
deformed, i.e. $[p_{i},p_{j}]=0$. Is then natural to assume the commutators
between $M_{ij}$ and $\tilde{x}_{k}$, as well as between $M_{ij}$ and $p_{k}$,
as undeformed. This way we deal with the (Euclidean) Snyder space [11].

We now consider a general rescaling of the non-commutative coordinates
$\tilde{x}_{i}$ in terms of a momentum-dependent function $\varphi\left(\alpha
p^{2}\right)$ as

$\tilde{x}_{i}=x_{i}\varphi\left(\alpha p^{2}\right),$ (2)

i.e. we consider a realization of the algebra (1) in terms of ordinary phase
space variables [12]. It is not difficult to show that the function $\varphi$
is uniquely fixed (up to a sign) by our natural assumptions and reads
$\varphi\left(\alpha p^{2}\right)=\sqrt{1\pm\alpha p^{2}}$. This way the
commutator between non-commutative coordinates and momenta is given by

$[\tilde{x}_{i},p_{j}]=i\delta_{ij}\sqrt{1\pm\alpha p^{2}}$ (3)

and the ordinary Heisenberg algebra is recovered as soon as $\alpha\rightarrow
0$. This deformed algebra closes in sense that all the Jacobi identities are
satisfied and can be related to the $\kappa$-Poincaré one [13]. Interest in
non-commutative (or deformed) phase space arises in order to mathematically
describe DSR and, in particular, some of DSR models can be formulated as
generalizations of Snyder model [14]. As last point, it is worth noting that
in the case of minus sign, the momentum is limited from above since $p\in
I\equiv\left(-1/\sqrt{\alpha},1/\sqrt{\alpha}\right)$. Therefore, in this
case, we have a truncation of the phase space at $p^{2}\geq\alpha$.

##  2 Friedmann dynamics in the deformed framework

The FRW cosmological models are characterized by imposing the isotropy on the
Cauchy surfaces which fill the space-time manifold. Isotropy reduces the phase
space of GR to be two dimensional with coordinates $(a,p_{a})$, where the
scale factor $a$ is the only degree of freedom of the system. It describe the
expansion of the Universe and the standard model of cosmology is based on this
models [15]. The dynamics of these Universes can be obtained from the extended
Hamiltonian

$\mathcal{H}_{E}=\frac{2\pi G}{3}N\frac{p_{a}^{2}}{a}+\frac{3}{8\pi G}Nak-
Na^{3}\rho+\lambda\pi,$ (4)

where $\lambda$ is a Lagrange multiplier and the parameter $k$ can be zero or
$\pm 1$ leading to the flat, open or closed Universe respectively. The term
$\lambda\pi$ is introduced since $\pi$, the momentum conjugate to the lapse
function $N$, vanishes. In the expression above $\rho=\rho(a)$ denotes a
generic energy density we have introduced into the dynamics.

Let us now consider the modifications induced on the dynamics of the FRW
models by the deformed Heisenberg algebra discussed above [8]. In particular,
we assume the symplectic structure of the minisuperspace as deformed and thus
the Poisson bracket (for any two-dimensional phase space function) appears to
be

$\\{F,G\\}_{\alpha}=\left(\frac{\partial F}{\partial a}\frac{\partial
G}{\partial p_{a}}-\frac{\partial F}{\partial p_{a}}\frac{\partial G}{\partial
a}\right)\sqrt{1\pm\alpha p_{a}^{2}}.$ (5)

We deal with a one-dimensional mechanical system and thus the only non-trivial
commutators is given by

$\\{a,p_{a}\\}=\sqrt{1\pm\alpha p_{a}^{2}}.$ (6)

Since the Poisson bracket $\\{N,\pi\\}=1$ is not affected by the deformations
induced by the $\alpha$ parameter on the system, the equations of motion
$\dot{N}=\\{N,\mathcal{H}_{E}\\}=\lambda$ and
$\dot{\pi}=\\{\pi,\mathcal{H}_{E}\\}=\mathcal{H}=0$ remain unchanged111As
usually, $\mathcal{H}=0$ is the scalar constraint and is obtained by requiring
the primary constraint $\pi=0$ will be satisfied at all times.. On the other
hand, the equations of motion of the scale factor $a$ and its conjugate
momentum $p_{a}$ become modified in such an approach via the deformed
symplectic geometry (5) and read

$\displaystyle\dot{a}$ $\displaystyle=$
$\displaystyle\\{a,\mathcal{H}_{E}\\}_{\alpha}=\frac{4\pi
G}{3}N\frac{p_{a}}{a}\sqrt{1\pm\alpha p_{a}^{2}},$ (7)
$\displaystyle\dot{p}_{a}$ $\displaystyle=$
$\displaystyle\\{p_{a},\mathcal{H}_{E}\\}_{\alpha}=N\left(\frac{2\pi
G}{3}\frac{p_{a}^{2}}{a^{2}}-\frac{3}{8\pi
G}k+3a^{2}\rho+a^{3}\frac{d\rho}{da}\right)\sqrt{1\pm\alpha p_{a}^{2}}.$

The equation of motion for the Hubble rate $(\dot{a}/a)$ can be obtained
solving the scalar constraint $\mathcal{H}=0$ with respect to $p_{a}$ and then
considering the first equation of (7). Explicitly it becomes

$\left(\frac{\dot{a}}{a}\right)^{2}=\left(\frac{8\pi
G}{3}\rho-\frac{k}{a^{2}}\right)\left[1\pm\frac{3\alpha}{2\pi
G}a^{2}\left(a^{2}\rho-\frac{3}{8\pi G}k\right)\right].$ (8)

We refer to this equation as the deformed Friedmann equation as it entails the
modification arising from the deformed Heisenberg algebra previously analyzed.
Of course, for $\alpha\rightarrow 0$ the ordinary Friedmann equation is
recovered. Let us consider the flat FRW Universe, i.e. the $k=0$ model. In
this case the deformed equation (8) appears to be

$\left(\frac{\dot{a}}{a}\right)^{2}=\frac{8\pi
G}{3}\rho\left(1\pm\frac{\rho}{\rho_{c}}\right),$ (9)

where $\rho_{c}=(2\pi G/3\alpha)\rho_{P}$ is the critical energy density, and
$\rho_{P}$ denotes the Planck one. When the limit $\alpha\rightarrow 0$ is
taken into account, the critical energy density diverges leading to the
ordinary dynamics. It is worth stressing that we have assumed the existence of
a fundamental minimal length. In fact, as widely accepted, one of the most
peculiar consequences of all promising quantum gravity theories is the
existence of a fundamental cut-off length, which should be related to the
Planck one [16]. Therefore, although this minimal length appears differently
in distinct contexts, it is reasonable that the scale factor (the energy
density) has a minimum (maximum) at the Planck scale.

The modified Friedmann equations (9) are known in literature. The one with the
$(-)$ deformation term is the effective equation incorporating the LQC effects
on the FRW dynamics [9]. It can be obtained using the geometric formulation of
quantum mechanics [17]. On the other hand, the string inspired Randall-Sundrum
braneworlds scenario leads to a modified Friedmenn equation as in (9) with the
$(+)$ sign [10]. The opposite sign of the $\rho^{2}$-term in such an equation,
is the well-known key difference between the effective LQC and the Randall-
Sundrum framework. In fact, the former approach leads to a non-singular
bouncing cosmology while in the latter, because of the positive sign, the
Hubble rate can not vanish and the Universe can not experiences a bounce (or
more generally a turn-around) in the scale factor.

##  3 Quantum mechanical implications of the deformed picture

As we have seen, the deformed algebra (3) leads to effective dynamics of loop
and braneworlds cosmologies in the minus or plus case respectively. Let us now
investigate some implications of the deformed framework in the quantum theory.
Firstly, we have to stress that the ($\pm$)-frameworks are, of course,
physically different. More precisely, the deformed Hilbert spaces
$\mathcal{F}_{\pm}$ underling the algebras (6) can be written as [8]

$\mathcal{F}_{\pm}=L^{2}\left(\mathbb{R}(I),dp_{a}/\sqrt{1\pm\alpha
p_{a}^{2}}\right),$ (10)

for the $\pm\alpha$ deformation of the ordinary Heisenberg theory,
respectively. It is worth noting that these Hilbert spaces are unitarily
inequivalent each other and also with respect to the ordinary one
$L^{2}(\mathbb{R},dp_{a})$. This is not surprising since the deformation of
the canonical commutation relations can be viewed, from the realization (2),
as an algebra homomorphism which is a non-canonical transformation and thus it
can not be implemented as an unitary transformation. New features are then
introduced at both classical and quantum level. (For an application of the
formalism to the harmonic oscillator problem see [8].)

A peculiar feature which deserves to be analyzed is the uncertainty principle
underlying the deformed symplectic structure (5). The generalized uncertainty
relation can be immediately obtained from the commutator (6) and reads

$\Delta a\Delta p_{a}\geq\frac{1}{2}|\langle\left(1\pm\alpha
p_{a}^{2}\right)^{1/2}\rangle|,$ (11)

by which, using the basic proprieties $\langle p_{a}^{2n}\rangle\geq\langle
p_{a}^{2}\rangle$ and $\langle p_{a}^{2}\rangle=(\Delta p_{a})^{2}+\langle
p_{a}\rangle^{2}$, the boundary of the allowed region begin

$\Delta a=\frac{1}{2}\left|\left(\frac{1\pm\alpha\langle
p_{a}\rangle^{2}}{(\Delta p_{a})^{2}}\pm\alpha\right)^{1/2}\right|.$ (12)

As we can easily see, for an infinite uncertainty in momentum (or better when
the relation $\Delta p_{a}\gg(\Delta
p_{a})^{\star}\equiv\sqrt{(1\pm\alpha\langle p_{a}\rangle)/\alpha}$ holds),
the uncertainty in the scale factor $a$ no longer vanishes but approaches the
minimal value of $\Delta a_{\text{min}}=\sqrt{\alpha}/2$. It is interesting to
note that, $\Delta a_{\text{min}}$ is the global minimum in the $(+)$-sector,
while $\Delta a_{\text{min}}=0$ is allowed in the $(-)$-one. This appears as
soon as the dispersion on its conjugate momentum $\Delta p_{a}$ reaches the
critical value of $(\Delta p_{a})^{\star}$.

Summarizing, in the $(+)$-sector a nonzero minimal uncertainty in the particle
(Universe) position (the scale factor) appears. The resulting implications are
quite profound. In fact, it is no longer possible to spatially localize a wave
function with arbitrary precision and then no physical states which are
position eigenstates exist at all since they were only formal ones [18]. As we
have seen, this framework leads to the same Friedamnn equation of the Randall-
Sundrum braneworlds scenario and thus, it is not unexpected that the plus
deformed uncertainty relation (11) contains, at the leading order in $\alpha$,
the string theory result $\Delta x\sim(1/\Delta p+l_{s}^{2}\Delta p)$ [19], in
which the string length $l_{s}$ can be identify with $\sqrt{\alpha/2}$.

On the other hand, to obtain the Friedmann equation found in the effective
loop cosmology, the $(-)$-deformed Heisenberg algebra is required. In this
case a vanishing uncertainty in position is allowed and therefore the position
eigenstates are true physical states (in the same sense of the ordinary
quantum mechanics). However, differently from the Heisenberg framework, an
infinite uncertainty in momentum is no longer required and $\Delta
x_{\text{min}}=0$ appears as soon as the finite value $(\Delta
p)^{\star}\propto 1/\sqrt{\alpha}$ is considered (we also remember that in
this scheme there is a cut-off on the momentum, i.e. $|p|\leq
1/\sqrt{\alpha}$). This way, considering the minus relation (11) at the first
order in $\alpha$, a generalized uncertainty principle for LQC can be proposed
to be $\Delta x\sim|1/\Delta p-l_{L}^{2}\Delta p|$, where
$l_{L}=\sqrt{\alpha/2}$ can be regarded as the loop cut-off length scale.

## Conclusions

The equations of motion of the FRW models obtained in LQC and in the
braneworlds scenario can be reproduced by a deformed Heisenberg algebra. This
algebra in the unique one which is consistent, in the sense of the Jacobi
identities, with the assumptions that both the translation and rotation groups
are undeformed and that the commutator between the non-commutative coordinates
is as in (1). Notably, it is also related to the $\kappa$-Poincaré algebra and
the only freedom in (2) lies in the $\pm$ sign. The $(+)$-framework leads to
the effective Friedmann dynamics of Randall-Sundrum braneworlds scenario,
while the opposite one to that of LQC. From this perspective, the former
framework is such that a vanishing uncertainty in position (the scale factor
of the Universe) is not longer allowed. On the other hand, the $(-)$-scheme
implies that the zero uncertainty in position appears for a finite uncertainty
in the momentum, proportional to the natural cut-off of the framework.
Summarizing, a non-commutative (deformed) picture which leads, at
phenomenological level, to the prediction of more general theories can be
formulated. The validity and applicability of this model to more complicated
(and physically interesting) arenas will deserve future investigations.

## References

## References

  * [1] M.R.Douglas and N.A.Nekrasov, Rev.Mod.Phys. 73 (2001) 977.
  * [2] S.Doplicher, K.Fredenhagen and J.E.Roberts, Phys.Lett.B 331 (1994) 39.
  * [3] G.Amelino-Camelia, Int.J.Mod.Phys.D 11 (2002) 35; Phys.Lett.B 510 (2001) 255; J.Magueijo and L.Smolin, Phys.Rev.Lett. 88 (2002) 190403.
  * [4] C.Rovelli, arXiv:0808.3505; L.Smolin, arXiv:0808.3765.
  * [5] M.Bojowald, Living Rev.Rel. 8 (2005) 11.
  * [6] A.Ashtekar, T.Pawlowski and P.Singh, Phys.Rev.Lett. 96 (2006) 141301; Phys.Rev.D 73 (2006) 124038.
  * [7] M.V.Battisti and G.Montani, Phys.Lett.B 656 (2007) 96; Phys.Rev.D 77 (2008) 023518; B.Vakili and H.R.Sepangi, Phys.Lett.B 651 (2007) 79; A.Bina, K.Atazadeh and S.Jalalzadeh, Int.J.Theor.Phys. 47 (2008) 1354; H.Garcia-Compean, O.Obregon and C.Ramirez, Phys.Rev.Lett. 88 (2002) 161301.
  * [8] M.V.Battisti, arXiv:0805.1178.
  * [9] P.Singh, Phys.Rev.D 73 (2006) 063508; P.Singh, K.Vandersloot and G.V.Vereshchagin Phys.Rev.D 74 (2006) 043510.
  * [10] R.Maartens, Living Rev.Rel. 7 (2004) 7.
  * [11] H.S.Snyder, Phys.Rev. 71 (1947) 38.
  * [12] S.Meljanac, M.Milekovic and S.Pallua, Phys.Lett.B 328 (1994) 55; L.Jonke and S.Meljanac, Phys.Lett.B 526 (2002) 149.
  * [13] M.Maggiore, Phys.Lett.B 304 (1993) 65; Phys.Rev.D 49 (1994) 5182.
  * [14] J.Kowalski-Glikman, Phys.Lett.B 547 (2002) 291; J.Kowalski-Glikman and S.Nowak, Class.Quant.Grav. 20 (2003) 4799.
  * [15] E.W.Kolb and M.S.Turner, The Early Universe (Adison-Wesley Reading, 1990).
  * [16] L.J.Garay, Int.J.Mod.Phys.A 10 (1995) 145.
  * [17] V.Taveras, arXiv:0807.3325.
  * [18] A.Kempf, G.Mangano and R.B.Mann, Phys.Rev.D 52 (1995) 1108,; A.Kempf, J.Math.Phys. 38 (1997) 1347.
  * [19] D.J.Gross and P.F.Mendle, Nucl.Phys.B 303 (1988) 407; K.Konishi, G.Paffuti and P.Provero, Phys.Lett.B 234 (1990) 276.


# Computing the broadcast time of a graph

Marika Ivanova<EMAIL_ADDRESS>Department of Theoretical Computer
Science and Mathematical Logic, Charles University, Prague, Czech Republic
Dag Haugland<EMAIL_ADDRESS>Department of Informatics, University of
Bergen, Norway  Bård Hennning Tvedt<EMAIL_ADDRESS>Department of
Physics, University of Bergen, Norway

(Received: date / Accepted: date)

###### Abstract

Given a graph and a subset of its nodes, referred to as source nodes, the
minimum broadcast problem asks for the minimum number of steps in which a
signal can be transmitted from the sources to all other nodes in the graph. In
each step, the sources and the nodes that already have received the signal can
forward it to at most one of their neighbor nodes. The problem has previously
been proved to be NP-hard. In the current work, we develop a compact integer
programming model for the problem. We also devise procedures for computing
lower bounds on the minimum number of steps required, along with methods for
constructing near-optimal solutions. Computational experiments demonstrate
that in a wide range of instances with sufficiently dense graphs, the lower
and upper bounds under study collapse. In instances where this is not the
case, the integer programming model proves strong capabilities in closing the
remaining gap.

###### keywords:

Broadcasting , Integer Programming , Bounds , Computational Experiments

††journal: Discrete Applied Mathematics

##  1 Introduction

Fast and efficient distribution of information gives rise to many optimization
problems of growing interest. Information dissemination processes studied in
the mathematical and algorithmic literature [8, 10, 15, 17] often fall into
one of the categories _gossiping_ or _broadcasting_. When all network nodes
control each their unique piece of information, and all pieces are to be
disseminated to all nodes, the process is called gossiping [2, 3]
Dissemination of the information controlled by one particular source node to
all network nodes is referred to as broadcasting [20, 23], and multicasting
[1] if a subset of the network nodes are information targets. If the
information is to be stored at the source, and assembled by pieces stored at
all other nodes, then the information flows in the reverse of the broadcasting
direction, and the dissemination process is _accumulation_. Broadcasting and
accumulation can both be generalized to processes where only a subset of the
nodes need to receive/disseminate information, while the remaining nodes are
available as transit units that pass the information on to neighboring nodes.

Information dissemination follows a certain _communication model_. In the
_whispering_ model, each node sends/receives information to/from at most one
other node in its vicinity at the time. The _shouting_ model corresponds to
the case where nodes communicate with all their neighbor nodes simultaneously.
Generalizing whispering and shouting, the communication can also be
constrained to neighbor subsets of given cardinality.

In the current work, a problem in the domain of broadcasting is studied. The
_minimum broadcast time_ (MBT) problem is identified by a graph and a subset
of its nodes, referred to as source nodes. Each node in the graph corresponds
to a communication unit. The task is to disseminate a signal from the source
nodes to all other nodes in a shortest possible time (broadcast time), while
abiding by communication rules. A node is said to be _informed_ at a given
time if it is a source, or it already has received the signal from some other
node. Otherwise, the node is said to be _uninformed_. Consequently, the set of
informed nodes is initially exactly the set of sources. Reflecting the fact
that communication can be established only between pairs of nodes that are
located within a sufficiently close vicinity of each other, the edge set of
the graph consists of potential communication links along which the signal can
be transmitted.

The time is divided into a finite number of steps. Agreeing with the
whispering model, every informed node can, in each time step, forward the
signal to at most one uninformed neighbor node. Therefore, the number of
informed nodes can at most be doubled from one step to the next. This
communication protocol appears in various practical application such as
communication among computer processors or telephone networks. In situations
where the signals have to travel large distances, it is typically assumed that
the signal is sent to one neighbor at the time. Inter-satellite communication
networks thus constitute a prominent application area [4]. Particularly, the
MBT problem arises when one or a few satellites need to broadcast data quickly
by means of time-division multiplexing.

The current literature on MBT offers some theoretical results, including
complexity and approximability theorems. Although inexact solution methods
also have been proposed, few attempts seem to be made in order to compute the
exact optimum, or to find lower bounds on the minimum broadcast time. The goal
of the current text is to fill this gap, and we make the following
contributions in that direction:

First, a compact integer programming model is developed. While the model
targets the exact minimum in instances of moderate size, its continuous
relaxation is suitable for computation of lower bounds in larger instances.
Second, we derive lower bounding techniques, both of an analytical nature and
in terms of a combinatorial relaxation of MBT, that do not rely on linear
programming. Third, we devise an upper bounding algorithm, which in
combination with the lower bounds is able to close the optimality gap in a
wide range of instances.

The remainder of the paper is organized as follows: Next, we review the
current scientific literature on MBT and related problems, and in Section 2, a
concise problem definition is provided. The integer program is formulated and
discussed in Section 3. Lower and upper bounding methods are derived in
Section 4 and 5, respectively. Computational experiments are reported in
Section 6, before the work is concluded by Section 7.

###  1.1 Literature overview

Deciding whether an instance of MBT has a solution with broadcast time at most
$t$ has been shown to be NP-complete [26]. For bipartite planar graphs with
maximum degree 3, NP-completeness persists even if $t=2$ or if there is only
one source [18]. When $t=2$, the problem also remains NP-complete for cubic
planar graphs [21], grid graphs with maximum degree 3, complete grid graphs,
chordal graphs, and for split graphs [18]. The single-source variant of the
decision version of MBT is NP-complete for grid graphs with maximum degree 4,
and for chordal graphs [18]. The problem is known to be polynomial in trees
[26]. Whether the problem is NP-complete for split graphs with a single source
was stated as an open questions in [18], and has to the best of our knowledge
not been answered yet.

A number of inexact methods, for both general and special graph classes, have
been proposed in the literature during the last three decades. One of the
first works of this category [24] introduces a dynamic programming algorithm
that identifies all maximum matchings in an induced bipartite graph.
Additional contributions of [24] include heuristic approaches for near optimal
broadcasting. Among more recent works, [14] describes a meta heuristic
algorithm for MBT, and provides a comparison with other existing methods. The
communication model is considered in an existing satellite navigation system
in [4], where a greedy inexact method is proposed together with a mathematical
programming model. Examples of additional efficient heuristics can be found
e.g. in [12, 11, 27].

Considerable attention was devoted to finding approximation algorithms for
MBT. In [19], the authors argue that methods presented in [24] provide no
guarantee on the performance, and show that wheel-graphs are examples of
unfavourable instances. Another contribution from [19] is an
$\mathcal{O}(\sqrt{n})$-additive approximation algorithm for broadcasting in
general graphs with $n$ nodes. The same work also provides approximation
algorithms for several graph classes with small separators with approximation
ratio proportional to the separator size times $\log n$. Authors of [23]
improve the approximation result by presenting a
$\mathcal{O}\left(\frac{\log^{2}n}{\log\log n}\right)$-approximation
algorithm, and thus remove the additive $\mathcal{O}(\sqrt{n})$ term.
Subsequently, [1] provides a $\mathcal{O}(\log n)$ approximation. This work
also shows that it is NP-hard to approximate MBT of any graph within a factor
of $3-\epsilon$. An algorithm with $\mathcal{O}\left(\frac{\log n}{\log\log
n}\right)$-approximation ratio given in [6] improves the result further. Most
of the works cited above consider a single source. (Throughout the current
text, the symbol $\log$ refers to the logarithm of base 2.)

A related problem extensively studied in the literature is the minimum
broadcast graph problem [9, 20]. A broadcast graph supports a broadcast from
any node to all other nodes in optimal time $\lceil\log n\rceil$. For a given
integer $n$, a variant of the problem is to find a broadcast graph of $n$
nodes such that the number of edges in the graph is minimized. In another
variant, the maximum node degree rather than the edge cardinality is subject
to minimization. MgGarvey et al. [20] study integer linear programming (ILP)
models for $c$-broadcast graphs, which is a generalization where signal
transmission to at most $c$ neighbours is allowed in a single time step.

Despite a certain resemblance with MBT, the minimum broadcast graph problem is
clearly distinguished from our problem, and will consequently not be
considered further in the current work.

##  2 Network Model and Definitions

The communication network is represented by a connected graph $G=(V,E)$ and a
subset $S\subseteq V$ referred to as the set of sources. We denote the number
of nodes and the number of sources by $n=|V|$ and $\sigma=|S|$, respectively.
The digraph with nodes $V$ and arcs $(u,v)$ and $(v,u)$ for each $\\{u,v\\}\in
E$ is denoted $\overrightarrow{G}=(V,\overrightarrow{E})$.

######  Definition 1.

The _broadcast time_ $\tau(G,S)$ of a node set $S\subseteq V$ in $G$ is
defined as the smallest integer $t\geq 0$ for which there exist a sequence
$V_{0}\subseteq\dots\subseteq V_{t}$ of node sets and a function
$\pi:V\setminus S\to V$, such that:

  1. 1.

$V_{0}=S$ and $V_{t}=V$,

  2. 2.

for all $v\in V\setminus S$, $\\{\pi(v),v\\}\in E$,

  3. 3.

for all $k=1,\ldots,t$ and all $v\in V_{k}$, $\pi(v)\in V_{k-1}$, and

  4. 4.

for all $k=1,\ldots,t$ and all $u,v\in V_{k}\setminus V_{k-1}$,
$\pi(u)=\pi(v)$ only if $u=v$.

Referring to Section 1, the node set $V_{k}$ is the set of nodes that are
informed in time step $k$. Initially, only the sources are informed
($V_{0}=S$), whereas all nodes are informed after $t$ time steps ($V_{t}=V$),
and the set of informed nodes is monotonously non-decreasing
($V_{k-1}\subseteq V_{k}$ for $k=1,\ldots,t$). The parent function $\pi$ maps
each node to the node from which it received the signal. Conditions 2–3 of
Definition 1 thus reflect that the sender is a neighbor node in $G$, and that
it is informed at an earlier time step than the recipient node. Because each
node can send to at most one neighbor node in each time step, condition 4
states that $\pi$ maps the set of nodes becoming informed in step $k$ to
distinct parent nodes. The preimage of $v$ under $\pi$, that is, the set of
child nodes of $v$, is denoted $\pi^{-1}(v)$.

The optimization problem in question is formulated as follows:

######  Problem 1 (Minimum Broadcast Time).

Given $G=(V,E)$ and $S\subseteq V$, find $\tau(G,S)$.

######  Definition 2.

For any $V_{0},\ldots,V_{t}$ and $\pi$ satisfying the conditions of Definition
1, possibly with the exception of $t$ being minimum, the corresponding
_broadcast forest_ is the digraph $D=(V,A)$, where
$A=\left\\{\left(\pi(v),v\right):v\in V\right\\}$. If $t$ is minimum, $D$ is
referred to as a _minimum_ broadcast forest. Each connected component of $D$
is a _communication tree_.

It is easily verified that the communication trees are indeed arborescences,
rooted at distinct sources, with arcs pointing away from the source. Let
$T(s)=\left(V(s),A(s)\right)$ denote the communication tree in $D$ rooted at
source $s\in S$, and let $T_{k}(s)$ be the subtree of $T(s)$ induced by
$V(s)\cap V_{k}$. Analogously, let $D_{k}$ be the directed subgraph of $D$
induced by node set $V_{k}$. For the sake of notational simplicity, the
dependence on $(V_{0},\ldots,V_{t},\pi)$ is suppressed when referring to the
directed graphs introduced here.

The degree of node $v$ in graph $G$ is denoted by $\deg_{G}(v)$. For a given
subset $U\subseteq V$ of nodes, we define $G[U]$ as the subgraph of $G$
induced by $U$. We let $\deg^{+}_{\overrightarrow{G}}(v)$ and
$\deg^{-}_{\overrightarrow{G}}(v)$ denote, respectively, the out-degree and
the in-degree of node $v$ in $\overrightarrow{G}$, and we let
$\deg_{\overrightarrow{G}}(v)=\deg_{\overrightarrow{G}}^{+}(v)+\deg_{\overrightarrow{G}}^{-}(v)$.
When $p$ is a logical proposition, $\delta_{p}=1$ if $p$ is true, and
$\delta_{p}=0$, otherwise.

##  3 Exact methods

In this section, we formulate an ILP model for Problem 1, and discuss possible
solution strategies.

###  3.1 Broadcast time model

Given an integer $t\geq\tau(G,S)$, define the variables
($(u,v)\in\overrightarrow{E}$, $k=1,\ldots,t$)

$x_{uv}^{k}=\begin{cases}1,\text{ if }v\in V_{k}\setminus V_{k-1}\text{ and
}\pi(v)=u,\\\ 0,\text{ otherwise},\end{cases}z_{k}=\begin{cases}1,\text{ if
}k\leq\tau(G,S),\\\ 0,\text{ otherwise}.\end{cases}$

Variable $x_{uv}^{k}$ thus represents the decision whether or not the signal
is to be transmitted from node $u$ to node $v$ in period $k$, while $z_{k}$
indicates whether transmissions take place as late as in period $k$.

An upper bound $t$ on the broadcast time $\tau(G,S)$ is easily available.
Because $G$ is connected, the cut between any set $V_{i}$ of informed nodes
and its complement is non-empty, and therefore at least one more node can be
informed in each period. It follows that $\tau(G,S)\leq n-\sigma$. The bound
is tight in the worst case instance where $S=\\{v_{1}\\}$, and $G$ is a path
with $v_{1}$ as one of its end nodes. Problem 1 is then formulated as follows:

$\displaystyle\min\sum\limits_{k=1}^{t}z_{k}$ (1a) $\displaystyle\text{s.
t.~{}~{}~{}}\sum\limits_{k=1}^{t}\sum\limits_{v\in N(u)}x_{vu}^{k}=1$
$\displaystyle u\in V\setminus S,$ (1b) $\displaystyle\sum\limits_{v\in
N(u)}x_{uv}^{k}\leq\sum\limits_{\ell=1}^{k-1}\sum\limits_{w\in
N(u)}x_{wu}^{\ell}$ $\displaystyle u\in V\setminus S,k=2,\dots,t,$ (1c)
$\displaystyle\sum\limits_{v\in N(u)}x_{uv}^{k}\leq z_{k}$ $\displaystyle u\in
V,k=1,\dots,t,$ (1d) $\displaystyle z_{k}\leq z_{k-1}$ $\displaystyle
k=2,\dots,t,$ (1e) $\displaystyle x_{uv}^{1}=0$
$\displaystyle(u,v)\in\overrightarrow{E},u\in V\setminus S,$ (1f)
$\displaystyle x_{uv}^{k}=0$ $\displaystyle(u,v)\in\overrightarrow{E},v\in
S,k=1,\ldots,t$ (1g) $\displaystyle
x\in\\{0,1\\}^{\overrightarrow{E}\times\\{1,\dots,t\\}},z\in\\{0,1\\}^{\\{1,\ldots,t\\}}.$
(1h)

By (1b), every non-source node $u$ receives the signal from exactly one
adjacent node $v$ in some time step $k$. The requirement that a non-source
node $u$ informs a neighbor $v$ in the $k$-th time step only if $u$ is
informed by some adjacent node $w$ in an earlier time step is modeled by (1c).
Constraints (1d) enforce that each node $u\in V$ forwards the signal to at
most one adjacent node $v$ in each time step. It also sets correct values to
the $z$-variable that appear in the objective function. The valid inequalities
1e reflect that $k\leq\tau(G,S)$ only if $k-1\leq\tau(G,S)$. Lastly,
constraints (1f) and (1g) state, respectively, that non-source nodes do not
transmit in the first time step, and that sources never receive the signal.

####  3.1.1 Decision version

The nature of MBT suggests another modelling approach derived from Model (1).
For a given positive integer $t$, we maximize the number of nodes $v$ that
receive a signal from some neighbor $u$ within $t$ time steps. Hence,
$\tau(G,S)$ is the smallest value of $t$ for which the maximum attains the
value $n-\sigma$. If the optimal objective function value is $n-\sigma$, the
corresponding values of the decision variable induce a broadcast forest with
broadcast time $t$. Otherwise, if the optimal objective function value is
smaller than $n-\sigma$, $t<\tau(G,S)$, and Model (2) is solved again with $t$
replaced by $t+1$. The computational efficiency of a search where $t$ is
increased from some lower bound on $\tau(G,S)$ is largely dependent of the
tightness of available upper and lower bounds on $\tau(G,S)$. If an upper
bound $\bar{t}\geq\tau(G,S)$ is known, and it is revealed that for
$t=\bar{t}-1$ fewer than $n-\sigma$ can receive the signal in time $t$, it is
concluded that $\tau(G,S)=\bar{t}$.

The decision version of a model for Minimum Broadcast Time takes the form

$\displaystyle\max\sum\limits_{v\in V\setminus S}\sum\limits_{u\in
N(v)}\sum\limits_{k=1}^{t}x_{uv}^{k}$ (2a) $\displaystyle\text{s.
t.~{}~{}~{}}\sum\limits_{k=1}^{t}\sum\limits_{v\in N(u)}x_{vu}^{k}\leq 1$
$\displaystyle u\in V\setminus S,$ (2b)
$\displaystyle\eqref{mod:basic:tIncreases},\eqref{mod:basic:positiveCost},\eqref{mod:basic:dec:0toSource},$
(2c) $\displaystyle x\in\\{0,1\\}^{\overrightarrow{E}\times\\{1,\dots,t\\}}.$
(2d)

In the transition from the optimization model (1), constraint (1b) is replaced
by (2b). The former is an inequality in the decision version, because not all
nodes are necessarily reached within the given time limit.

##  4 Lower bounds

Strong lower bounds on the minimum objective function value are of vital
importance to combinatorial optimization algorithms. In this section, we study
three types of lower bounds on the broadcast time $\tau(G,S)$.

###  4.1 Analytical lower bounds

Any solution $\left(V_{0},\ldots,V_{t},\pi\right)$ satisfying conditions 1–4
of Definition 1, also satisfies $\left|V_{k+1}\right|\leq 2\left|V_{k}\right|$
for all $k\geq 0$. Combined with the observation made in Section 3.1.1, this
yields the following bounds:

######  Observation 1.

For all instances $(G,S)$ of Problem 1,

$\left\lceil\log\frac{n}{\sigma}\right\rceil\leq\tau(G,S)\leq n-\sigma.$ (3)

Consider the $m$-step Fibonacci numbers
$\left\\{f^{m}_{k}\right\\}_{k=1,2,\ldots}$ [22], a generalization of the
well-known (2-step) Fibonacci numbers, defined by $f^{m}_{k}=0$ for $k\leq 0$,
$f^{m}_{1}=1$, and other terms according to the linear recurrence relation

$\displaystyle f^{m}_{k}$ $\displaystyle=\sum\limits_{j=1}^{m}f^{m}_{k-j},$
$\displaystyle\text{ for }k\geq 2.$

The generalized Fibonacci numbers are instrumental in the derivation of a
lower bound on $\tau(G,S)$, depending on the maximum node degree
$d=\max\left\\{\deg_{G}(v):v\in V\right\\}$ in $G$. The idea behind the bound
is that the broadcast time can be no shorter than what is achieved if the
following ideal, but not necessarily feasible, criteria are met: Every source
transmits the signal to a neighbor node in each of the periods $1,\ldots,d$,
and every node $u\in V\setminus S$ transmits the signal to a neighbor node in
each of the first $d-1$ periods following the period when $u$ gets informed.
An exception possibly occurs in the last period, as there may be fewer nodes
left to be informed than there are nodes available to inform them.

######  Proposition 2.

$\tau(G,S)\geq\min\left\\{t:2\sigma\sum\limits_{j=1}^{t}f^{d-1}_{j}\geq
n\right\\}.$

###### Proof.

Consider a solution $\left(V_{0},\ldots,V_{t},\pi\right)$ with associated
broadcast graph $D$, such that $V_{0}\neq V_{1}\neq\cdots\neq V_{t-1}\neq
V_{t}$,

  * •

conditions 1 and 3–4 of Definition 1 are satisfied,

  * •

for each source $u\in S$ and each $j=1,\ldots,\min\\{d,t-1\\}$, there exists a
node $v\in V_{j}\setminus V_{j-1}$ such that $\pi(v)=u$, and

  * •

for each $k\in\\{1,\ldots,t-2\\}$, each node $u\in V_{k}\setminus V_{k-1}$,
and each $j=k+1,\ldots,\min\\{k+d-1,t-1\\}$, there exists a node $v\in
V_{j}\setminus V_{j-1}$ such that $\pi(v)=u$.

That is, all sources send the signal to some uninformed node (not necessarily
a neighbor node) in all periods up to $\min\\{d,t-1\\}$. All nodes that
received the signal in period $k$, forward it to some uninformed node in all
periods up to $\min\\{d-1,t-1\\}$, and all nodes are informed in period $t$.
Because condition 2 of Definition 1, stating that the flow of information
follows $E$, is not imposed, such a solution
$\left(V_{0},\ldots,V_{t},\pi\right)$ exists for an appropriate choice of $t$.
Since the solution implies that every node is actively receiving or sending
for up to $d$ consecutive periods, until the signal is broadcasted in period
$t$, it follows that $\tau(G,S)\geq t$. It remains to prove that the chosen
$t$ is the smallest value satisfying $2\sigma\sum_{k=1}^{t}f_{k}^{d-1}\geq n$,
i.e., that $2\sigma\sum_{k=1}^{t-1}f_{k}^{d-1}<n\leq
2\sigma\sum_{k=1}^{t}f_{k}^{d-1}$.

For $k=1,\ldots,t$, let $L_{k}=\left\\{v\in V_{k}:\deg_{D_{k}}(v)=1\right\\}$
denote the set of nodes with exactly one out- or in-neighbor in $D_{k}$, and
let $L_{k}=\emptyset$ for $k\leq 0$. That is, for $k>1$, $L_{k}$ is the set of
nodes that receive the signal in period $k$, whereas $L_{1}$ consists of all
nodes informed in period 1, including the sources $S$. Hence,
$L_{1},\ldots,L_{t-1}$ are disjoint sets (but $L_{t}$ may intersect
$L_{t-1}$), and $V_{k}=L_{1}\cup\cdots\cup L_{k}$ for all $k=1,\ldots,t$.

Consider a period $k\in\\{2,\ldots,t-1\\}$. The assumptions on
$\left(V_{0},\ldots,V_{t},\pi\right)$ imply that $\pi$ is a bijection from
$L_{k}$ to $L_{k-1}\cup\cdots\cup L_{k-d+1}$. Thus,
$\left|L_{k}\right|=\sum_{j=1}^{d-1}\left|L_{k-j}\right|$. Since also
$\left|L_{1}\right|=2\sigma=2\sigma f_{1}^{d-1}$ and
$\left|L_{j}\right|=f_{j}^{d-1}=0$ for $j\leq 0$, we get
$\left|L_{k}\right|=2\sigma f_{k}^{d-1}$. Further,
$\left|L_{t}\right|\leq\sum_{j=1}^{d-1}\left|L_{t-j}\right|=2\sigma
f_{t}^{d-1}$. It follows that
$2\sigma\sum_{k=1}^{t-1}f_{k}^{d-1}=\sum_{k=1}^{t-1}\left|L_{k}\right|=\left|V_{t-1}\right|<n=\left|V_{t}\right|\leq\sum_{k=1}^{t}\left|L_{k}\right|\leq
2\sigma\sum_{k=1}^{t}f_{k}^{d-1}$, which completes the proof. ∎

###  4.2 Continuous relaxations of integer programming models

For $t\in\mathbb{Z}_{+}$, define
$\Omega(t)\subseteq[0,1]^{\overrightarrow{E}\times\\{1,\ldots,t\\}}$ as the
set of feasible solutions to the continuous relaxation of (2a)–(2d), and let

$\Omega^{=}(t)=\left\\{x\in\Omega(t):\sum\limits_{u\in
N(v)}\sum\limits_{k=1}^{t}x_{uv}^{k}=1~{}~{}(v\in V\setminus S)\right\\}.$

Let
$t^{\ast}=\min\left\\{t\in\mathbb{Z}_{+}:\Omega^{=}(t)\neq\emptyset\right\\}$
be the smallest value of $t$ for which the optimal objective function value in
the relaxation equals $n-\sigma$. Existence of $t^{\ast}$ follows directly
from $\Omega^{=}\left(\tau(G,S)\right)\neq\emptyset$.

The continuous relaxation of (1a)–(1h) is feasible for sufficiently large $t$.
We denote its optimal objective function value by $\zeta(t)$.

######  Proposition 3.

For all $t\in\mathbb{Z}_{+}$ such that $\Omega^{=}(t)\neq\emptyset$,
$\zeta(t)\leq t^{\ast}\leq\tau(G,S)$.

###### Proof.

We first prove that $\zeta(t)$ is non-increasing with increasing $t$: Let
$\Gamma(t)$ denote the set of feasible solutions to the continuous relaxation
of (1a)–(1h), and assume $(x,z)\in\Gamma(t)$. Define
$\hat{x}\in[0,1]^{\overrightarrow{E}\times\\{1,\ldots,t+1\\}}$ such that for
all $(u,v)\in\overrightarrow{E}$, $\hat{x}_{uv}^{k}=x_{uv}^{k}$ ($k\leq t$)
and $\hat{x}_{uv}^{t+1}=0$. An analogous extension of $z$ to
$\hat{z}\in[0,1]^{\\{1,\ldots,t+1\\}}$ yields
$(\hat{x},\hat{z})\in\Gamma(t+1)$, and
$\sum_{k=1}^{t+1}\hat{z}_{k}=\sum_{k=1}^{t}z_{k}$ proves that
$\zeta(t+1)\leq\zeta(t)$.

For $t\in\mathbb{Z}_{+}$ such that $\Omega^{=}(t)\neq\emptyset$, $t\geq
t^{\ast}$ thus implies $\zeta(t)\leq\zeta(t^{\ast})\leq t^{\ast}$, where the
latter inequality follows from (1a) and $z_{1},\ldots,z_{t^{\ast}}\leq 1$. The
proof is complete by observing that $t^{\ast}\leq\tau(G,S)$ follows from
$\Omega^{=}\left(\tau(G,S)\right)\neq\emptyset$. ∎

######  Remark 4.

To compute a lower bound on $\tau(G,S)$, Proposition 3 suggests to solve a
sequence of instances of the continuous relaxation of problem (2a)–(2d), and
stop by the first value of $t=1,2,\ldots$ for which the optimal objective
function value is $n-\sigma$. Such an approach yields a lower bound
($t^{\ast}$) on $\tau(G,S)$, which is no weaker than the bound achieved by
solving the continuous relaxation of (1a)–(1h).

######  Remark 5.

Remark 4 also applies to a reformulation of (1a)–(1h), where a unique integer
variable $y$ replaces $z_{1},\ldots,z_{t}$, and the objective is to minimize
$y$ subject to the constraints $y\geq\sum\limits_{k=1}^{t}k\sum\limits_{u\in
N(v)}x_{uv}^{k}~{}~{}(v\in V\setminus S)$, (1b)–(1c), and (1f)–(1h).

###  4.3 Combinatorial relaxations

Lower bounds on the broadcast time $\tau(G,S)$ are obtained by omitting one or
more of the conditions imposed in Definition 1. For the purpose of strongest
possible bounds, the relaxations thus constructed can be supplied with
conditions that are redundant in the problem definition. Conditions 1–4 of
Definition 1 imply that

  1. 5.

for all $v\in V$, $\left|\pi^{-1}(v)\right|\leq\deg_{G}(v)-\delta_{v\in
V\setminus S}$.

A lower bound on $\tau(G,S)$ is then given by the solution to:

######  Problem 2 (Node Degree Relaxation).

Find the smallest integer $t\geq 0$ for which there exist a sequence
$V_{0}\subseteq\dots\subseteq V_{t}$ of node sets and a function
$\pi:V\setminus S\to V$, satisfying conditions 1 and 3–5.

Observe that the bound given in Proposition 2 is obtained by exploiting the
lower-bounding capabilities of the Node Degree Relaxation. By considering the
degree of all nodes $v\in V$, rather than just the maximum degree, stronger
bounds may be achieved in instances where $G$ is not regular ($\min_{v\in
V}\deg_{G}(v)<\max_{v\in V}\deg_{G}(v)$).

Denote the source nodes $S=\left\\{v_{1},\dots,v_{\sigma}\right\\}$ and the
non-source nodes $V\setminus S=\left\\{v_{\sigma+1},\ldots,v_{n}\right\\}$,
where
$\deg_{G}(v_{\sigma+1})\geq\deg_{G}(v_{\sigma+2})\geq\dots\geq\deg_{G}(v_{n})$,
and let $d_{i}=\deg_{G}(v_{i})$ ($i=1,\ldots,n$). Thus,
$\left\\{d_{1},\ldots,d_{n}\right\\}$ resembles the conventional definition of
a non-increasing degree sequence of $G$, with the difference that only the
subsequence consisting of the final $n-\sigma$ degrees is required to be non-
increasing.

For a given $t\in\mathbb{Z}_{+}$, consider the problem of finding
$\left(V_{0},\ldots,V_{t},\pi\right)$ such that $V_{0}=S$, conditions 3–5 are
satisfied, and $\left|V_{t}\right|$ is maximized. The smallest value of $t$
for which the maximum equals $n$ is obviously the solution to Problem 2.

The algorithm for Problem 2, to follow later in the section, utilizes that the
maximum value of $\left|V_{t}\right|$ is achieved by transmitting the signal
to nodes in non-increasing order of their degrees. Observe that, contrary to
the case of Problem 1, transmissions to non-neighbors are allowed in the
relaxed problem. Any instance of Problem 2 thus has an optimal solution where,
for $k=1,\ldots,t-1$, $u\in V_{k}\setminus V_{k-1}$ and $v\in V_{k+1}\setminus
V_{k}$ implies $\deg_{G}(u)\geq\deg_{G}(v)$.

A rigorous proof of this follows next.

######  Lemma 6.

The maximum value of $\left|V_{t}\right|$ over all
$\left(V_{0},\ldots,V_{t},\pi\right)$ satisfying $V_{0}=S$ and conditions 3–5,
is attained by some $\left(V_{0},\ldots,V_{t},\pi\right)$ where
$\min\left\\{i:v_{i}\in V_{k}\setminus V_{k-1}\right\\}>\max\left\\{i:v_{i}\in
V_{k-1}\right\\}$ ($k=1,\ldots,t$).

###### Proof.

Consider an arbitrary optimal solution $\left(V_{0},\ldots,V_{t},\pi\right)$,
and assume that $v_{i}\in V_{p}\setminus V_{p-1}$, $v_{j}\in V_{q}\setminus
V_{q-1}$, $i<j$, and $1\leq q<p\leq t$. We prove that the solution obtained by
swapping nodes $v_{i}$ and $v_{j}$ is also optimal. Let $\bar{V}_{k}=V_{k}$
for $k=0,\ldots,q-1,p,p+1,\ldots,t$, and
$\bar{V}_{k}=\left(V_{k}\setminus\\{v_{j}\\}\right)\cup\\{v_{i}\\}$ for
$k=q,\ldots,p-1$. Because $\left|\bar{V}_{t}\right|=\left|V_{t}\right|$, we
only need to show that $\left(\bar{V}_{0},\ldots,\bar{V}_{t},\bar{\pi}\right)$
is feasible for some $\bar{\pi}$. In the following, we demonstrate that a
valid parent function $\bar{\pi}$ can be obtained by swapping $\pi(v_{i})$ and
$\pi(v_{j})$, along with a simple adjustment ensuring that
$\left|\bar{\pi}^{-1}(v_{j})\right|\leq\left|\pi^{-1}(v_{j})\right|$.

Define
$m=\max\left\\{0,\left|\pi^{-1}(v_{i})\right|-\left|\pi^{-1}(v_{j})\right|\right\\}$.
Consider the case where $m>0$. Because $v_{i}$ has at most one child in each
$V_{k}\setminus V_{k-1}$ ($k=p+1,\ldots,t$), there exist
$p_{1}>\cdots>p_{m}>p$, and $u_{r}\in V_{p_{r}}\setminus V_{p_{r}-1}$
($r=1,\ldots,m$) such that $\pi(u_{r})=v_{i}$, whereas $v_{j}$ has no child in
$\bigcup_{r=1}^{m}\left(V_{p_{r}}\setminus V_{p_{r}-1}\right)$. Let
$U=\\{u_{1},\ldots,u_{m}\\}$, and let $U=\emptyset$ if $m=0$.

Let $\bar{\pi}(v)=v_{i}$ for all $v\in U$, and $\bar{\pi}(v)=v_{j}$ for all
$v\in\pi^{-1}(v_{i})\setminus U$. Also, let $\bar{\pi}(v)=v_{i}$ for all
$v\in\pi^{-1}(v_{j})\setminus\\{v_{i}\\}$. If $\pi(v_{i})=v_{j}$, let
$\bar{\pi}(v_{j})=v_{i}$, otherwise let $\bar{\pi}(v_{j})=\pi(v_{i})$. Let
$\bar{\pi}(v_{i})=\pi(v_{j})$. For all other non-source nodes, that is, all
$v\in V\setminus S$ for which $v_{i}\neq\pi(v)\neq v_{j}$, let
$\bar{\pi}(v)=\pi(v)$.

If $m>0$,
$\left|\bar{\pi}^{-1}(v_{i})\right|=\left|\pi^{-1}(v_{i})\right|\leq\deg_{G}(v_{i})-1$
and
$\left|\bar{\pi}^{-1}(v_{j})\right|=\left|\pi^{-1}(v_{j})\right|\leq\deg_{G}(v_{j})-1$.
Otherwise,
$\left|\bar{\pi}^{-1}(v_{i})\right|=\left|\pi^{-1}(v_{j})\right|\leq\deg_{G}(v_{j})-1\leq\deg_{G}(v_{i})-1$,
and
$\left|\bar{\pi}^{-1}(v_{j})\right|=\left|\pi^{-1}(v_{i})\right|\leq\left|\pi^{-1}(v_{j})\right|\leq\deg_{G}(v_{j})-1$.
For $v_{i}\neq v\neq v_{j}$,
$\left|\bar{\pi}^{-1}(v)\right|=\left|\pi^{-1}(v)\right|$, and thus
$\left(\bar{V}_{0},\ldots,\bar{V}_{t},\bar{\pi}\right)$ satisfies condition 5.
It is straightforward to show that
$\left(\bar{V}_{0},\ldots,\bar{V}_{t},\bar{\pi}\right)$ also satisfies
condition 3–4 ∎

Alg. 1 takes as input the number $\sigma$ of sources and the number $n$ of
nodes, along with the vertex degrees $d_{1},\ldots,d_{n}$, where
$d_{\sigma+1}\geq\cdots\geq d_{n}$. It operates with a counter $\nu$ of
informed nodes, initiated to $\sigma$. Thus, nodes $v_{1},\ldots,v_{\nu}$ are
informed, whereas $v_{\nu+1},\ldots,v_{n}$ are not. A counter denoted $a_{i}$
($i=1,\ldots,n$) keeps track of the number of nodes informed by node $v_{i}$.
The set $F$ consists of indices $i$ of informed nodes that still have not sent
the signal to $d_{i}-1$ nodes ($d_{i}$ nodes if $i\leq\sigma$). In each
iteration of the outer loop of the algorithm, all nodes $v_{i}$ for which
$i\in F$, informs some currently uninformed node, and all counters are updated
accordingly. The process stops when all $n$ nodes are informed, and the number
of performed iterations is returned.

Data: $\sigma,n,d_{1},\ldots,d_{n}\in\mathbb{Z}_{+}$

1 $a_{1}\leftarrow\cdots\leftarrow a_{n}\leftarrow 0$, $\nu\leftarrow\sigma$

2 for  _$t=1,2,\dots$_ do

3 $F\leftarrow\left\\{i=1,\ldots,\nu:a_{i}<d_{i}-\delta_{i>\sigma}\right\\}$

4 for $i\in F$ do $a_{i}\leftarrow a_{i}+1$

5 $\nu\leftarrow\nu+|F]$

6 if $\nu\geq n$ return $t$

7

8 end for

Algorithm 1 Lower bound exploiting the degree distribution

######  Proposition 7.

Alg. 1 returns a lower bound on $\tau(G,S)$.

###### Proof.

Follows from Lemma 6 and the subsequent discussion. ∎

##  5 Upper bounds

Access to an upper bound $\bar{t}\geq\tau(G,S)$ affects the number of
variables in the models studied in Section 3.1. Particularly in the decision
version (2), the iterative approach can be terminated once the solution is
found to be infeasible for broadcast time limit $\bar{t}-1$. Algorithms that
output feasible, or even near-optimal solutions, are instrumental in the
computation of upper bounds. Further, such methods are required in
sufficiently large instances, where exact approaches fail to terminate in
practical time.

###  5.1 Existing heuristic methods

Building on earlier works [12, 13], Harutyunyan and Jimborean [11] study a
heuristic (considering $\sigma=1$) departing from a shortest-path tree of $G$.
A sequence of local improvements is performed in the bottom-up direction in
the tree, starting by the leafs and terminating at the root node.
Rearrangements of the parent assignments are made in order to reduce the
broadcast time needed in subtrees. The heuristic has running time
$\mathcal{O}\left(|E|\log{n}\right)$.

###  5.2 A construction method

Consider an integer $t^{\prime}\geq 0$, node sets $S=V_{0}\subseteq
V_{1}\subseteq\cdots\subseteq V_{t^{\prime}}\neq V$ and a function
$\pi:V\setminus S\mapsto V$, where $\left\\{\pi(v),v\right\\}\in E$ for all
$v\in V_{t^{\prime}}\setminus S$, and conditions 3–4 of Definition 1 are
satisfied for $t=t^{\prime}$. That is,
$\left(V_{0},\ldots,V_{t^{\prime}},\pi\right)$ defines a broadcast forest
corresponding to the instance $\left(G\left[V_{t^{\prime}}\right],S\right)$,
but the forest does not cover $V$. In particular, if $t^{\prime}=0$, the
broadcast forest is a null graph on $S$, while it is a matching from $S$ to
$V_{1}\setminus S$ if $t^{\prime}=1$.

This section addresses the problem of extending the partial solution
$\left(V_{0},\ldots,V_{t^{\prime}},\pi\right)$ by another node set
$V_{t^{\prime}+1}$, such that the conditions above also are met for
$t=t^{\prime}+1$. With $t^{\prime}=0$ as departure point, a sequence of
extensions results in a broadcast forest corresponding to instance $(G,S)$.
Each extension identifies a matching from $V_{t^{\prime}}$ to $V\setminus
V_{t^{\prime}}$, and all matched nodes in the latter set are included in
$V_{t^{\prime}+1}$. A key issue is how to determine the matching.

Since the goal is to minimize the time (number of extensions) needed to cover
$V$, a _maximum cardinality_ matching between $V_{t^{\prime}}$ and $V\setminus
V_{t^{\prime}}$ is a natural choice. Lack of consideration of the matched
nodes’ capabilities to inform other nodes is however an unfavorable property.
Each iteration of Alg. 2 rather sees $k\geq 1$ time periods ahead, and
maximizes the total number of nodes in $V\setminus V_{t^{\prime}}$ that can be
informed in periods $t^{\prime}+1,\ldots,t^{\prime}+k$. Commitment is made for
only one period, and the matched nodes are those that are informed in period
$t^{\prime}+1$ from some node in $V_{t^{\prime}}$. The maximization problem in
question is exactly the one addressed by model (2), where $V_{t^{\prime}}$ is
considered as sources, $k$ the upper bound on the broadcast time, and the
graph is $G$ with all edges within $V_{t^{\prime}}$ removed. Choosing $k=1$
corresponds to the maximum matching option, whereas large values of $k$ (e.g.,
$k=n-\sigma$) makes Alg. 2 an exact method.

Data: $G=(V,E),S\subseteq V,k\in\\{1,\dots,n-\sigma\\}$

1 for  _$t^{\prime}=0,1,\dots$_ do

2 if $S=V$ return $t^{\prime}$

3 $x\leftarrow$ optimal solution to the instance of model (2) with $t=k$

4 for  _$\\{u,v\\}\in E$ such that $u\in S$, $v\in V\setminus S$, and
$x_{uv}^{1}=1$_ do

5 $S\leftarrow S\cup\\{v\\}$

6 end for

7

8 end for

Algorithm 2 Construction of near-optimal solutions through sequences of
matchings

In many instances, there are multiple options for selecting an optimal
solution $x$ (line 3). Two different sequences of solutions generated during
the course of Alg. 2 may result in different broadcast times. Let us take a
hypercube $C_{j}$ as an example which has $\tau(C_{j},S)=j$ for $\sigma=1$
regardless of selection of the source node. Alg. 2 with $k=1$ always finds
$\tau(C_{j},S)$ for $j=1\dots 3$. It also finds the optimum for $j\geq 4$
provided that the subgraph induced by the current $S$ at the beginning of each
iteration $t^{\prime}$ forms a hypercube $C_{t^{\prime}}$. If this tie-
breaking rule is violated, the algorithm may fail to find the optimum as
demonstrated in $C_{4}$ (TODO: image or description in the text?)

Intuitively, the broadcast time found by Alg. 2 is likely to be closer to the
optimum for larger $k$. This intuition is also confirmed by a vast majority of
instances in the experimental section. Nevertheless, there are instances for
which Alg. 2 with smaller $k$ finds a better solution. One such example is a
tree $T$ on 17 nodes with one source $s$ and $\text{deg}(s)=2$. The first
neighbor $n_{1}$ of $s$ is a root of a binomial tree $B_{2}$ of degree two.
One of the leafs of $B_{2}$ is an endpoint of a path of length 3. The second
neighbor $n_{2}$ of $s$ is adjacent to a root of binomial tree $B_{3}$. Alg. 2
with $k=3$ decides that $n_{1}\in V_{1}$, $n_{2}\in V_{2}$ and eventually
finds $\tau{T,\left\\{s\right\\}}$. With $k=5$, $n_{1}\in V_{2}$, $n_{2}\in
V_{1}$, which results in a suboptimal solution. (TODO: is such an example
useful? Should there be an illustration?)

######  Remark 8.

If $k=1$, then the running time of Alg. 2 is
$\mathcal{O}\left(n^{\frac{3}{2}}|E|\right)$, because the number of iterations
is no more than $n$, and the maximum cardinality matching is found in
$\mathcal{O}\left(\sqrt{n}|E|\right)$ time [16]. For fixed $k=2$, the problem
solved in each iteration is NP-hard [18].

######  Remark 9.

If $k=1$, no attempt is made to favor the nodes with many uninformed
neighbors. To that end, maximum cardinality matching can be replaced by
maximum _vertex-weight_ matching (MVM), where each node $v\in V\setminus S$ is
assigned the weight $1+\left|\left\\{u\in V\setminus S:\\{u,v\\}\in
E\right\\}\right|$. Other weights reflecting the capability of node $u$ to
inform other nodes in later periods could also be considered. The running time
of Alg. 2 increases to $\mathcal{O}\left(n^{2}|E|\right)$, as MVM is solved in
$\mathcal{O}\left(n|E|\right)$ time [5]. An approximate MVM-solution within
$\frac{2}{3}$ of optimality is found in $\mathcal{O}\left(|E|+n\log{n}\right)$
time [5].

##  6 Experimental Results

The aim of our experiments is to evaluate computational abilities of B&B
applied to the studied model, and determine its usability on different
instance types. Also, we assess the strength of upper and lower bounding
methods discussed above, as well as continuous relaxations of the models.

In some of the experimental settings we use randomly generated instances. The
generating procedure takes a number of nodes and a parameter $p$ as an input.
First, it generates a random tree with the given number of nodes. It then
iterates over all pairs of nodes that are not yet connected by an edge, and
places an edge between them with the probability $p$.

Apart from randomly generated instances, we also evaluate data sets of various
sizes and densities available online [25]. These existing collections of
instances are used as benchmarks for algorithms for the minimum Steiner tree
problem. We evaluate datasets named “I160”, “I320” and “I640” with selected
edge cardinalities stated in the tables with results. The only source node in
these instances is always the node with id 1. In each instance category, 20
graphs are available.

###  6.1 Comparison of upper and lower bounds

In the first set of experiments we study how does the strength of different
methods depend on the parameter $p$. We generate random single and double-
source instances of sizes 125, 250, 500 and 1000 with increasing $p$. Tabs. 1
and 2 summarize the results of randomly generated instances. Each entry is
calculated as an average from 100 instances for a given $n$, $p$ and a
selected method. Results obtained for existing instances are stated in Tab. 3
where 20 instances are used for obtaining average objective function value for
each instance category. Instead of the parameter $p$, the number of edges is
given in the second column.

The column ’fib’ consists of Fibonacci bounds. The values are rarely higher
than the trivial logarithmic bound. Lower bound obtained from degree sequence
in the column ’deg’ is slightly better, but in majority of cases is far weaker
than the LP bound, which is very tight in all considered experimental
settings. Upper bounds UB-$t$, $t=1,\dots 4$ are obtained using Alg. 2, which
takes $t$ as one of its input parameters. In general, we observe that the
higher $t$, the tighter upper bound is calculated. There are however some
instances where it does not hold, particularly for instances with larger $p$,
but the differences is very small, and can be explained as a coincidence.

We further observe that the span of bounds decreases with increasing $p$,
within one instance size, and also increases for a constant $p$ with
increasing instance size. The experiments were not pursued for higher values
of $p$, because it is very common that upper and lower bounds ’deg’ and ’UB-4’
coincide. This behavior is easy to explain. There are more possibilities how
to relay a signal in dense graphs as compared to sparser graphs. It is
therefore likely that denser graphs have optimal broadcast time close to the
lower bounds. The decreasing span of bounds is also noticeable with increasing
instance size.

Note that due to the computational time restriction, results in columns ’OPT’
are in fact lower bounds, whenever an interruption occurs. If the iterative
decision procedure is interrupted, it is not guaranteed that the number of
iterations performed is the optimal value. This is apparent in Tab. 3 in
instances with $n=640$ and $\sigma=960$. The LP relaxation of the model
provides a tighter lower bound in average than the integer model.

Instance |  | Lower bounds |  | Upper bounds
---|---|---|---|---
$n$ | $p$ |  | fib | deg | LP | OPT | UB-4 | UB-3 | UB-2 | UB-1
125 | 0.001 |  | 7.23 | 8.35 | 16.46 | 16.49 | 18.72 | 20.28 | 20.77 | 23.75
0.002 |  | 7.21 | 8.20 | 13.97 | 13.98 | 15.80 | 17.18 | 17.21 | 19.50
0.004 |  | 7.03 | 8.08 | 11.44 | 11.49 | 13.07 | 14.06 | 14.30 | 16.05
0.008 |  | 7.00 | 7.86 | 9.09 | 9.22 | 10.71 | 11.25 | 11.85 | 12.90
0.016 |  | 7.00 | 7.59 | 7.94 | 8.01 | 9.11 | 9.42 | 9.83 | 10.58
250 | 0.001 |  | 8.01 | 9.29 | 16.18 | 16.28 | 18.72 | 20.09 | 20.49 | 23.22
0.002 |  | 8.00 | 9.17 | 12.87 | 12.93 | 15.23 | 16.19 | 16.84 | 18.78
0.004 |  | 8.00 | 8.92 | 10.06 | 10.33 | 12.23 | 12.87 | 13.46 | 14.70
0.008 |  | 8.00 | 8.83 | 8.96 | 9.03 | 10.31 | 10.73 | 11.34 | 12.18
0.016 |  | 8.00 | 8.24 | 8.24 | 8.24 | 9.40 | 9.42 | 9.71 | 10.51
500 | 0.001 |  | 9.01 | 10.20 | 14.35 | 14.54 | 17.06 | 18.47 | 18.92 | 20.96
0.002 |  | 9.00 | 9.95 | 11.19 | 11.55 | 13.69 | 14.54 | 15.11 | 16.53
0.004 |  | 9.00 | 9.86 | 10.09 | 10.12 | 11.81 | 12.12 | 12.69 | 13.57
0.008 |  | 9.00 | 9.33 | 9.42 | 9.43 | 10.53 | 10.71 | 11.07 | 11.84
0.016 |  | 9.00 | 9.00 | 9.00 | 9.00 | 10.00 | 9.94 | 10.00 | 11.06
1000 | 0.001 |  | 10.00 | 10.92 | 12.39 | 12.83 | 15.44 | 16.39 | 17.08 | 18.49
0.002 |  | 10.00 | 10.77 | 11.06 | 11.07 | 12.99 | 13.38 | 14.00 | 14.98
0.004 |  | 10.00 | 10.41 | 10.54 | 10.57 | 11.80 | 11.93 | 12.06 | 13.06
0.008 |  | 10.00 | 10.01 | 10.01 | 10.01 | 11.02 | 11.02 | 11.02 | 12.04
0.016 |  | 10.00 | 10.00 | 10.00 | 10.00 | 10.11 | 10.06 | 10.13 | 12.00
Table 1: Objective function values yielded by different methods of randomly generated instances with $\sigma=1$ Instance |  | Lower bounds |  | Upper bounds
---|---|---|---|---
$n$ | $p$ |  | fib | deg | LP | OPT | UB-4 | UB-3 | UB-2 | UB-1
125 | 0.001 |  | 6.26 | 7.10 | 13.33 | 13.35 | 15.20 | 16.70 | 16.88 | 19.23
0.002 |  | 6.20 | 7.04 | 11.96 | 11.99 | 13.57 | 14.67 | 14.92 | 17.11
0.004 |  | 6.04 | 7.01 | 9.75 | 9.77 | 11.14 | 12.05 | 12.36 | 13.73
0.008 |  | 6.00 | 6.96 | 7.78 | 7.91 | 9.19 | 9.71 | 10.21 | 11.38
0.016 |  | 6.00 | 6.78 | 6.90 | 6.97 | 8.10 | 8.27 | 8.62 | 9.40
250 | 0.001 |  | 7.03 | 8.14 | 14.59 | 14.63 | 16.92 | 18.07 | 18.40 | 20.67
0.002 |  | 7.00 | 8.01 | 11.46 | 11.51 | 13.40 | 14.32 | 14.7 | 16.61
0.004 |  | 7.00 | 7.98 | 8.99 | 9.16 | 10.94 | 11.57 | 12.11 | 13.29
0.008 |  | 7.00 | 7.86 | 7.98 | 7.99 | 9.22 | 9.61 | 10.08 | 10.89
0.016 |  | 7.00 | 7.26 | 7.27 | 7.27 | 8.33 | 8.35 | 8.61 | 9.44
500 | 0.001 |  | 8.00 | 9.04 | 12.82 | 12.96 | 15.47 | 16.47 | 17.05 | 18.86
0.002 |  | 8.00 | 8.98 | 10.12 | 10.29 | 12.38 | 13.24 | 13.91 | 15.11
0.004 |  | 8.00 | 8.87 | 8.98 | 8.99 | 10.61 | 11.03 | 11.47 | 12.41
0.008 |  | 8.00 | 8.54 | 8.56 | 8.56 | 9.50 | 9.67 | 9.96 | 10.79
0.016 |  | 8.00 | 8.09 | 8.09 | 8.09 | 8.98 | 8.94 | 8.98 | 10.05
1000 | 0.001 |  | 9.00 | 10.00 | 11.23 | 11.44 | 14.02 | 14.79 | 15.56 | 16.95
0.002 |  | 9.00 | 9.01 | 9.02 | 9.03 | 9.18 | 9.14 | 9.21 | 11.06
0.004 |  | 9.00 | 9.51 | 9.59 | 9.61 | 10.83 | 10.97 | 11.10 | 12.06
0.008 |  | 9.00 | 9.03 | 9.03 | 9.03 | 10.00 | 10.00 | 10.00 | 11.01
0.016 |  | 9.00 | 9.00 | 9.00 | 9.00 | 9.12 | 9.07 | 9.15 | 11.00
Table 2: Objective function values yielded by different methods of randomly generated instances with $\sigma=2$ Instance |  | Lower bounds |  | Upper bounds
---|---|---|---|---
$n$ | $p$ |  | fib | deg | LP | OPT | UB-4 | UB-3 | UB-2 | UB-1
160 | 240 |  | 8.00 | 8.00 | 8.05 | 8.05 | 10.10 | 10.90 | 11.20 | 12.55
160 | 320 |  | 8.00 | 8.00 | 8.00 | 8.00 | 9.30 | 9.70 | 10.05 | 10.85
320 | 480 |  | 9.00 | 9.00 | 9.05 | 9.20 | 11.60 | 12.60 | 12.85 | 14.75
320 | 640 |  | 9.00 | 9.00 | 9.00 | 9.00 | 10.40 | 10.85 | 11.20 | 12.25
640 | 960 |  | 10.00 | 10.00 | 10.11 | 10.00 | 13.06 | 13.94 | 14.67 | 16.39
640 | 1280 |  | 10.00 | 10.00 | 10.00 | 10.00 | 12.00 | 12.25 | 12.85 | 13.80
Table 3: Objective function values yielded by different methods of existing
instances available online with $\sigma=1$

###  6.2 Solution time

Average solution time of instances from the previous section is reported in
Tabs. 4 and 5.. The columns LP and OPT consists of solution times of solving
LP relaxation and B&B applied to the ILP model, respectively. The column
’int.’ consists of the percentage of instances of which solving was
interrupted after 1 hour, before the optimal solution was found. Each
interrupted instance counts with 3600 to the resulting average solution time.
The values in the last column ’col.’ are the numbers of instances in which the
upper and lower bounds collapsed. I.e., how many instances have the lower
bound ’deg’ value equal to the upper bound ’UB-4’ value. In these instances,
the optimal solution is not pursued, because its objective function value is
already known. Values in the second last column are therefore the proportion
of interruptions in the total number of instances to which B&B is actually
applied (in which the bounds do not collapse).

All investigated instances of size up to 500 nodes are solved to optimality
within the imposed 1 hour time limit. The resulting times are not reported for
sparse instance sets of size 125 and 250 in Tab 4 because in the worst case it
takes 3 seconds to solve an instance to optimality, and interruptions or bound
collapses never occur. Computation of B&B on instances of 1000 nodes is
frequently interrupted before the optimal solution is found, particularly
those with large $p$. Even thought the objective function value decreases with
increasing $p$, and so the decision procedure needs to perform less
iterations, overall solution time often increases. However, there are some
exceptions in the monotonous growth of the solution time. Instances with
$n=1000$ and $p=0.001$ in average take more time than instances with $n=1000$
and $p=0.002$. Similar behavior is exhibited in existing instances, where
solution time tends to be longer for sparser graphs. It is also obvious and in
accordance with the intuition that in denser graphs, the upper and lower
bounds collapse more often.

Instance |  | $\sigma=1$ |  | $\sigma=2$
---|---|---|---|---
$n$ | $p$ |  | LP | OPT | int. | col. |  | LP | OPT | int. | col.
125 | 0.016 |  | 0 | 1 | 0 | 4 |  | 0 | 1 | 0 | 9
250 | 0.008 |  | 1 | 4 | 0 | 2 |  | 0 | 3 | 0 | 1
0.016 |  | 1 | 17 | 0 | 20 |  | 1 | 13 | 0 | 34
500 | 0.001 |  | 3 | 7 | 0 | 0 |  | 2 | 5 | 0 | 0
0.002 |  | 2 | 26 | 0 | 0 |  | 2 | 22 | 0 | 0
0.004 |  | 3 | 53 | 0 | 0 |  | 2 | 26 | 0 | 0
0.008 |  | 6 | 214 | 0 | 13 |  | 4 | 101 | 0 | 0
0.016 |  | 11 | 390 | 0 | 10 |  | 6 | 212 | 0 | 11
1000 | 0.001 |  | 12 | 1366 | 30 | 0 |  | 9 | 866 | 17 | 0
0.002 |  | 20 | 814 | 17 | 0 |  | 24 | 378 | 0 | 0
0.004 |  | 56 | 1637 | 33 | 10 |  | 69 | 1647 | 30 | 8
0.008 |  | 101 | 3399 | 75 | 6 |  | 107 | 3378 | 74 | 30
0.016 |  | 172 | 3600 | 100 | 89 |  | 235 | 3600 | 100 | 88
Table 4: Solution time in seconds of LP relaxation and B&B of randomly generated instances $n$ | $|E|$ | LP | OPT | int. | col.
---|---|---|---|---|---
160 | 240 | 0 | 2 | 0 | 0
160 | 320 | 0 | 1 | 0 | 0
320 | 480 | 1 | 227 | 0 | 0
320 | 640 | 1 | 17 | 0 | 0
640 | 960 | 3 | 3155 | 85 | 0
640 | 1280 | 5 | 236 | 0 | 0
Table 5: Solution time in seconds of LP relaxation and B&B of existing
instances available online for $\sigma=1$

##  7 Concluding Remarks

This work focuses on the minimum broadcast time problem and presents several
techniques for determining lower bounds, upper bounds as well as optimal
solutions. The main contribution consists in introducing an ILP model and a
suitable solving method. Its LP relaxation provides a strong lower bound which
often coincides with the optimum, and is stronger than other lower bounding
methods presented in this work in vast majority of test instances. We consider
various instance types and sizes both from existing datasets and randomly
generated.

We also develop and test a heuristic method that provides an upper bound.
Large instances that are too time consuming for B&B can often be solved to
optimality by comparing objective function values yielded by LP relaxation and
upper bounding methods. The results of numerical experiments indicate that
instances with many edges are more time consuming to solve by B&B. At the same
time, however, the denser graph, the more likely are the upper and lower
bounds to coincide.

There is a potential for the future research in developing stronger upper
bounding algorithms and improving the existing ILP model. The problem
definition assumes that a node transmits a signal to at most one neighbor in
each time step. A further direction of the research considers a generalization
of the problem, where nodes can transmit a signal to up to a certain number of
neighbors at the same time.

## References

  * [1] Bar-Noy, A., Guha, S., Naor, J., Schieber, B., Multicasting in heterogeneous networks, SIAM Journal on Computing, 30, 2, 347–358, 2000
  * [2] Bermond, J., Gargano, L., Perennes, S., Optimal sequential gossiping by short messages, Discrete Applied Mathematics 86(1998) 145–155
  * [3] Bermond, J., Gargano, L., Rescigno, A.A., Vaccaro, U., Fast gossiping by short messages, Lecture Notes in Computer Science 944(1995) 135–146.
  * [4] Chu, X., Chen, Y., Time division inter-satellite link topology generation problem: Modeling and solution, International Journal of Satellite Communications and Networking, 194 – 206, 36 (2017)
  * [5] Dobrian, F., Halappanavar, M., Pothen, A., Al–Herz, A., A 2/3-approximation algorithm for vertex weighted matching in bipartite graphs, SIAM Journal of Scientific Computing, 41(1)(2019) A566–A591.
  * [6] Elkin, M., Kortsarz, G., Sublogarithmic approximation for telephone multicast: path out of jungle, Symposium on Discrete Algorithms, 76 – 85 (2003)
  * [7] Farley, A. M., Proskurowski, A., Broadcasting in Trees with Multiple Originators, SIAM Journal on Algebraic Discrete Methods 2(4) (1981) 381–386.
  * [8] Fraigniaud, P., Lazard, E., Methods and problems of communication in usual networks, Discrete Applied Mathematics, 53, 1–3, 79–133, 1994.
  * [9] Grigni, M., Peleg, D., Tight bounds on minimum broadcast networks Networks, 207-222, 4 (1991)
  * [10] Harutyunyan, H.A., Liestman, A.L., Peters, J.G., Richards, D., Broadcasting and gossiping, In Thulasiraman, K., Arumugam, S., Brandstädt, A., Nishizeki, T. (eds): Handbook of Graph Theory, pp. 1477–1494. Chapman and Hall, 2013.
  * [11] Harutyunyan, H.A., Jimborean, C., New Heuristic for Message Broadcasting in Network, IEEE 28th International Conference on Advanced Information Networking and Application, 517 – 524, (2014)
  * [12] Harutyunyan, H.A., Shao, B., An efficient heuristic for broadcasting in networks, Journal of Parallel and Distributed Computing, 68 – 76, 66, 1 (2006)
  * [13] Harutyunyan, H.A., Wang, W, Broadcasting Algorithm Via Shortest Paths, 16th International Conference on Parallel and Distributed Systems (ICPADS), pp. 299–305, 2010, doi: 10.1109/ICPADS.2010.110.
  * [14] Hasson, Y., Sipper, M., A Novel Ant Algorithm for Solving the Minimum Broadcast Time Problem, International Conference on Parallel Problem Solving from Nature, 775 – 780 (2004)
  * [15] Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L., A survey of gossiping and broadcasting in communication networks, Networks, 18(4):319–349, 1988.
  * [16] Hopcroft, J.E., Karp, R.M., An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs, SIAM Journal on Computing, 2(4)(1973) 225–23.
  * [17] Hromkovič, J., Klasing, R., Monien, B, Peine, R., Dissemination of Information in Interconnection Networks (Broadcasting & Gossiping), In: Du DZ., Hsu D.F. (eds) Combinatorial Network Theory, Applied Optimization, vol 1, pp. 125–212. Springer, Boston, MA, 1996.
  * [18] Jansen, K., Müller, H., The minimum broadcast time problem for several processor networks, Theoretical Computer Science, 69 – 85, 147 (1995)
  * [19] Kortsarz, G., Peleg, D., Approximation algorithms for minimum-time broadcast SIAM Journal on Discrete Mathematics, 401 – 427, 8, 3 (1995)
  * [20] McGarvey, R. G., Rieksts, B. Q., Ventura, J. A., Ahn, N., Binary linear programming models for robust broadcasting in communication networks, Discrete Applied Mathematics, 173 – 84, 204, (2016)
  * [21] Middendorf, M., Minimum broadcast time is NP-complete for 3-regular planar graphs and deadline 2, Information Processing Letters, 281 – 287, 46 (1993)
  * [22] Noe, T. D., Post, J. V., Primes in Fibonacci n-step and Lucas n-Step Sequences, J. Integer Seq. 8, Article 05.4.4, 2005.
  * [23] Ravi, R., Rapid rumor ramification: Approximating the minimum broadcast time, Proceedings 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, USA, 1994, pp. 202-213, doi: 10.1109/SFCS.1994.365693.
  * [24] Scheuermann, P., Wu, G., Heuristic Algorithms for Broadcasting in Point-to-Point Computer Networks, IEEE Transactions on Computers, 804 – 811, 33, 9 (1984)
  * [25] http://steinlib.zib.de/download.php
  * [26] Slater, P. J., Cockayne, E. J., Hedetniemi, S.T., Information dissemination in Trees, SIAM Journal on Computing, 692 – 701, 10, 4 (1981)
  * [27] Wang, W., Heuristics for Message Broadcasting in Arbitrary Networks, Master thesis, Concordia University, Montréal, Québec, Retrieved from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.633.5827&rep=rep1&type=pdf (2010)