Minimum Broadcast Time

• INSTANCE: Graph $G=(V,E)$ and a source node $v_0\in V$ .

• SOLUTION: A broadcasting scheme. At time 0 only $v^0$ contains the message that is to be broadcast to every vertex. At each time step any vertex that has received the message is allowed to communicate the message to at most one of its neighbours.

• COST FUNCTION: The broadcast time, i.e., the time when all vertices have received the message.

• OBJECTIVE: Minimize.

• Approx.: Approximable within $O(\log^2 \vert V\vert/\log\log\vert V\vert)$ [96].

• Hardness: NP-hard [52].

• Comment: Approximable within $2B$ if the degree of $G$ is bounded by a constant $B$ [96]. Approximable within $O(\log V)$ if $G$ is chordal, $k$ -outerplanar [78]. Approximable within $O(\log\vert V\vert/\log\log\vert V\vert)$ if $G$ has bounded tree width [88].