On the Complexity of Telephone Broadcasting
from Cacti to Bounded Pathwidth Graphs

We explain how single-br($G,s$) operates. Observe that removing the source vertex $s$ partitions $G$ into one or more disjoint connected components. By the definition of cactus graphs, each of these connected components contains at most two neighbors of $s$ (see [1] for details). We refer to a connected component with one neighbor (respectively two neighbors) of $s$ as a single-neighbor (respectively double-neighbor) component.

single-br($G,s$) computes the broadcast time of each single-neighbor component $C$ recursively by computing single-br($C,u$), where $u$ is the single neighbor of $s$ in $C$. Similarly, it computes the broadcast time of each double-neighbor component $C$ by computing double-br($C,u,v$), where $u,v$ are neighbors of $s$ in $C$. After calculating all these broadcasting times, single-br($G,s$) sorts these values in non-increasing order and informs the neighbors of $s$ in this order. For that, it uses a regular call for single-neighbor components and a super-call for double-neighbor components. In other words, single-br($G,s$), informs the component with the largest broadcasting time in the first round, the component with the second largest broadcast time next, and so on. This is reminiscent of broadcasting in trees [11], except that super-calls are used for double components. Let $b_i$ denote the broadcast time of the $i$’th component $C_i$ in this order.

The total broadcasting time for single-br(G,s) is then computed as ${\max }_i(i+b_i)$, which will be the output of single-br(G,s).

Next, we describe double-br($G,s_1,s_2$). Let $P$ be the unique path between $s_1$ and $s_2$. In any broadcast tree $T$ of double-br, some vertices on $P$ are informed through $s_1$ and some through $s_2$. Thus, exactly one edge $e\in P$ is excluded from the tree. After removing such $e$, the graph $G$ will be partitioned into two disjoint connected components $G_1^e$ and $G_2^e$, which are respectively informed through $s_1$ and $s_2$ (See Figure 2). The method double-br works by removing the edge $e^{\ast }$ with a minimum value of $\max \{\text{single-br}(G_1^e,s_1),\text{single-br}(G_2^e,s_2)\}$ over all $e\in P$.

Next, we explain how double-br finds $e^{\ast }$. An exhaustive approach that tries all edges $e\in P$ and calls single-br twice per edge may take exponential time. To fix this, double-br works in two phases:

• $\mathrm{■}$

  In Phase $1$, the method pre-computes the broadcast time for the connected subgraphs of $G$ after removing vertices of $P$ from $G$. Every resulting connected component after removing $P$ has at most two neighbors in $P$ [1]. For any single-neighbor component $C$ with vertex $s$ connected to $P$, single-br($C,s$) is computed recursively. Similarly, for any double-neighbor component with vertices $s_1,s_2$ connected to $P$, double-br($C,s_1,s_2$) is computed recursively.

• $\mathrm{■}$

  Next, we describe Phase $2$. At each iteration of Phase $2$, we fix an edge $e=(u,v)\in P$ and aim to compute single-br($G_1^e,s_1$) and single-br($G_2^e,s_2$), where $u\in G_1^e$ and $v\in G_2^e$. We explain how to efficiently compute single-br($G_1^e,s_1$). Finding single-br($G_2^e,s_2$) is done similarly. Let $⟨u(=u_1),u_2,\mathrm{\dots },u_k(=s_1)⟩$ be the sequence of vertices in the unique path from $u$ to $s_1$. Let $H_i^e$ be the connected component of $G$ that contains $u_i$ after removing the edge ($u_i,u_{i+1}$) from $G_1^e$. Note that $H_k^e=G_1^e$. We compute $b_i=$single-br($H_i^e,u_i$) using the values computed in Phase $1$ as follows in an iterative manner from $i=1$ to $i=k$.

  Consider all connected components of $H_i^e$ after removing $u_i$. Note that, for $i>1$, $H_{i-1}^e$ is one of these components. Consider the set $B$ of broadcast times for all these components, with the neighbor(s) of $u_i$ as the source(s) of broadcast. All these values are computed in Phase $1$ except for $b_{i-1}$, which is computed in the previous iteration. double-br sorts $B$ in non-increasing order of broadcast times and informs neighbors of $u_i$ accordingly (similar to single-br). As a result, in the $i$’th iteration, the broadcast time $b_i$ is computed as ${\max }_{j\in [B]}(j+B[j])$. At iteration $i=k$, we compute $b_k$, which is indeed single-br($G_1^e,s_1$) [1].

Figure 2 provides an illustration.

First, we show that Cactus Broadcaster runs in $𝒪(n^3\log n)$. This can be established using induction on the size of the input graph, based on the recursive nature of the algorithm. Details can be found in [1].

Second, we show that Cactus Broadcaster has an approximation factor of $2$. Intuitively, single-br with super-calls runs no longer than an optimal broadcast scheme without super-calls; this is because every super call only expedites informing one of the two sources of broadcasting in double-neighbor components. As mentioned earlier, a broadcast scheme with super calls can be simulated with a scheme (without super-calls) that completes no later than twice the number of rounds. On the other hand, the selection of edge $e^{\ast }$ by double-br ensures that $\max (\text{single-br(}{G}_1^{e^{\ast }},s_1\text{)},\text{single-br(}{G}_2^{e^{\ast }},s_2\text{)})\le \max (\text{single-br(}{G}_1^{e^{+}},s_1\text{)},\text{single-br(}{G}_2^{e^{+}},s_2\text{)})$, where $e^{+}$ is the edge that is absent in the optimal broadcast tree of $G$. A formal proof follows from an inductive argument on the input size [1]. $◀$

The approximation factor given by Theorem 6 is tight. Consider a graph $G$ formed by $t$ triangles that all share an endpoint $s$. The broadcasting time of Cactus Broadcaster on $(G,s)$ is $2t$ as its broadcast tree will be a star with $2t$ leaves, while the optimal broadcast tree completes broadcasting in $t+1$ rounds ($s$ will have degree $t$). Thus, the approximation factor tends to $2$ for large $t$.

Suppose we are given an instance $\varphi =(X,C)$ of $3,4$-SAT. We construct an instance ${ℐ}_{\varphi }$ of TwIS as follows. For each variable $x_i\in X$, form a pair of $(X_i,\overline{X_i})$ of twin intervals, each of length $7$, where $X_i=[16i-15,16i-8]$ and ${\overline{X}}_i=[16i-7,16i]$. We refer to $X_i$ (respectively $\overline{X_i}$) as the principal interval of literal $x_i$ (respectively $\neg x_i$). The length $7$ of these intervals allows for placing up to $4$ non-crossing unit intervals, each of length $1$, within the principal interval; these intervals will be used for clause gadgets, as we will explain. For each clause $C_j$, we define three interval twin pairs $(I_k^j,\overline{I_k^j})$, each associated with one of the literals of ${\mathrm{\ell }}_k^j\in C_j$ for each $k\in [3]$. Suppose ${\mathrm{\ell }}_k^j$ is the $p$’th literal where its corresponding variable $x_i\in X$ appears ($p\in [4]$). If ${\mathrm{\ell }}_k^j$ is a positive (respectively negative) literal of variable $x_i$, then define $I_k^j$ as a unit interval starting at $16i-7+2(p-1)$ (respectively, starting at $16i-15+2(p-1)$). Intuitively, $I_k^j$ is defined as one of the four-unit intervals within the principal interval of $\neg x$. Meanwhile, $\overline{I_k^j}$ is $[16n+2j,16n+2j+1]$ for all $k\in [3]$. Finally, to define the restriction function, we let $r(t)=1$ for all $t\le 16n$ and $r(t)=2$, otherwise. Figure 3 illustrates an example of the above reduction.

We provide an intuitive explanation of why this reduction works. The formal proof can be found in [1]. We argue that a satisfying assignment to instance $\varphi$ of the 3,4-SAT problem bijects to a satisfying interval selection for the instance ${ℐ}_{\varphi }$ of TwIS. The bijection requires that for any literal $\mathrm{\ell }$ that is true in a satisfying assignment of $\varphi$, the principal interval of $\mathrm{\ell }$ is selected in the solution for ${ℐ}_{\varphi }$.

The restrictions imposed by $r$ imply that whenever a principal interval of a literal $\mathrm{\ell }$ is selected, the unit intervals associated with (up to 4) occurrences of $\neg \mathrm{\ell }$ cannot be selected (because $r(t)=1$ in their intersecting points). Thus, whenever the principal interval of a literal $\mathrm{\ell }$ is selected (i.e., its twin, which is the principal interval of $\neg \mathrm{\ell }$ is not selected), one can select the unit intervals associated with any occurrence of $\mathrm{\ell }$ in clauses where it appears; this is because they intersect with the principal interval of $\neg \mathrm{\ell }$, which is not selected. Selecting these unit intervals means their twin unit intervals This yields an equivalent between a satisfying assignment in the SAT formula and the TwIS. We further note that the number of twin intervals in ${ℐ}_{\varphi }$ is polynomial in $|X|$ and $|C|$. We can conclude the following lemma, which establishes the hardness of TwIS in the strong sense based on the above reduction.

Given an arbitrary instance $ℐ=(I,r,m^{\prime })$ of TwIS, where $|I|=n^{\prime }$ for some positive $n^{\prime }$, we construct the corresponding instance $𝒟=(D,m)$ of DoSePr as follows. For each twin pair of intervals $(I_i,\overline{I_i})\in I$, where $I_i=(a^{\prime },b^{\prime })$ and $\overline{I_i}=(c^{\prime },d^{\prime })$, we construct a regular dome $D_i=(a_i,b_i,c_i,d_i)$ where $a_i=6n^{\prime }{a}^{\prime },b_i=6n^{\prime }{b}^{\prime }+3n^{\prime },c_i=6n^{\prime }{c}^{\prime },$ and $d_i=6n^{\prime }{d}^{\prime }+3n^{\prime }$. It is easy to verify that $D_i$ is indeed a dome, that is $b_i-a_i=d_i-c_i$ [1].

We define $m$ to be a large enough horizon. In particular, we let $m=164{(n^{\prime }{m}^{\prime })}^2$. For any $t\in [m]$ that is a multiple of $6n^{\prime }$ and $t\le 3n^{\prime }(2m^{\prime }+1)$, we further add $d(t)$ some singleton domes that all start at $t$ and end at $m$. In other words, we add $d(t)$ identical singleton domes $(t,m)$. Next, we explain how $d(t)$ is defined. For convenience, we let $d(t)=0$ if $t$ is not a multiple of $6n^{\prime }$ or $t>3n^{\prime }(2m^{\prime }+1)$. Suppose $t$ is indeed a multiple of $6n^{\prime }$. The idea is to define $d(t)$ in a way to project the requirements imposed by the restriction function $r$ in $ℐ$ to the requirement ${𝒩}_S(t)\le t$ in DoSePr.

Let ${𝔇}_i^t$ be the set of regular domes with exactly $i$ endpoints before or at point $t$, and define $c(t)=2|{𝔇}_4^t|+|{𝔇}_3^t|+|{𝔇}_2^t|$.

Intuitively, this definition of $c$ implies that there are $c(t)$ arc endpoints with value at most $t$ in any valid solution $S$ (a set of arcs), regardless of the choices made to form $S$. This is because:

• $\mathrm{■}$

  (i) all arc endpoints of domes in ${𝔇}_4^t$ are at most $t$, and two of them (associated with one arc) contribute to $c(t)$.

• $\mathrm{■}$

  (ii) three arc endpoints of domes in ${𝔇}_3^t$ are at most $t$, and any such dome contributes at least 1 to $c(t)$.

• $\mathrm{■}$

  (iii) the left endpoints of both arcs of domes in ${𝔇}_2^t$, and since one arc is in $S$, the dome contributes exactly $1$ to $c(t)$.

Finally, we let

The scaling argument that is applied when forming the DoSePr instance from TwIS instance ensures that $d(t)$ is indeed non-negative for any $t\in [m]$ (see [1] for details). This completes our construction of the DoSePr instance. In a nutshell, we have added one regular dome per twin interval in the TwIS instance, and for any $t\in [m]$, we added extra identical singleton domes to capture the requirements imposed by the restriction function in the TwIS instance.

We provide some intuitions about the correctness of the reduction. A formal proof can be found in [1]. We show that any valid solution $S$ for instance $𝒟$ of DoSePr bijects to a valid solution $S^{\prime }$ of $ℐ$. Note that $S$ contains exactly one arc, the inner or the outer arc, of each regular dome $D_i$ of $𝒟$ (in addition to singleton domes, which are contained in any valid solution for $𝒟$). Now, $S^{\prime }$ selects the left interval $I_i$ when the outer arc of $D_i$ is selected in $S$ and the right interval $\overline{I_i}$ when the inner arc of $D_i$ is selected in $S$ (see Figure 4). We let ${\mathrm{\Gamma }}_{S^{\prime }}(t^{\prime })$ denote the number of intervals selected by $S^{\prime }$ that include $t^{\prime }\in [m^{\prime }]$. We show that $S$ is a valid solution for $𝒟$ if and only if $S^{\prime }$ is a valid solution to $ℐ$.

Suppose $S$ is a valid solution for DoSePr. Then we must have ${𝒩}_S(t)\le t$ for any $t\in [m]$, where ${𝒩}_S(t)$ is the number of arc endpoints in $S$ with value at most $t$. As mentioned earlier, $c(t)$ endpoints will be present in any valid solution regardless of the choices to form $S$. Moreover, $S$ must contain all endpoints of singleton domes in $𝒟$ for $j\le t$. That is, any valid solution for $𝒟$, including $S$, must contain $c(t)+{\sum }_{j\le t}d(j)$ arc endpoints. In addition to these fixed points, there will be more arcs in $S$, which are contributed by the domes in ${𝔇}_1^t$ and ${𝔇}_3^t$ as follows. Let $D_i$ be a regular dome in $𝒟$, and let $(I_i,{\overline{I}}_i)$ be its corresponding twin intervals in $ℐ$.

• $\mathrm{■}$

  Suppose $D_i\in {𝔇}_1^t$. Now, if $S$ contains the inner arc of $D_i$, the contribution of $D_i$ to ${𝒩}_S(t)$ would be $0$. This is equivalent to including the right interval $\overline{I_i}$ in $S^{\prime }$, and thus the twin interval $(I_i,\overline{I_i})$ does not contribute ${\mathrm{\Gamma }}_{S^{\prime }}(t^{\prime })$ for $t^{\prime }=t/6n$. Informally, the contribution of the dome $D_i$ to the left-hand side of inequality $N_S(t)\le t$ and the contribution of $(I_i,\overline{I_i})$ to the left-hand side of the inequality ${\mathrm{\Gamma }}_{S^{\prime }}(t^{\prime })\le r(t^{\prime })$ will be both $0$. Similarly, if $S$ contains the outer arc of $D_i$, the contribution of $D_i$ to ${𝒩}_S(t)$ would be $1$. This is equivalent to including the left interval $\overline{I_i}$ in the TwIS instance, and $(I_i,\overline{I_i})$ contribute $1$ item to ${\mathrm{\Gamma }}_{S^{\prime }}(t^{\prime })$. Informally, the contribution of the dome $D_i$ to the left-hand side of inequality ${𝒩}_S(t)\le t$ and the contribution of $(I_i,\overline{I_i})$ to the left-hand side of ${\mathrm{\Gamma }}_{S^{\prime }}(t/(6n^{\prime }))\le r(t^{\prime })$ will be both $1$.

• $\mathrm{■}$

  Suppose $D_i\in {𝔇}_3^t$. Assume $S$ contains the inner (respectively the outer) arc of $D_i$. In this case, in addition to the fixed $1$ unit of the contribution of $D_i$ to ${𝒩}_S(t)$ (captured in $c(t)$), it further contributes $1$ (respectively $0$) unit to ${𝒩}_S(t)$. This is equivalent to including the right interval ${\overline{I}}_i$ (respectively the left interval $I_i$) in $S^{\prime }$. In this case, the number of selected intervals in $S^{\prime }$ that intersect $t$ is increased by $1$ (respectively $0$). Intuitively, both left-hand sides of ${𝒩}_S(t)\le t$ and ${\mathrm{\Gamma }}_{S^{\prime }}(t/(6n^{\prime }))\le r(t^{\prime })$ increase by $1$ (respectively $0$).

We note that $n=|D|$ is polynomial in both $n^{\prime }$ and $m^{\prime }$, and thus $m=164{(n^{\prime }{m}^{\prime })}^2$ is polynomial $n$. Therefore, we can conclude the following lemma, which establishes the NP-hardness of DoSePr.

Given an instance $𝒟=(D,m)$ of DoSePr we construct an instance $𝒯=(G,r,\rho =2m)$ of Telephone Broadguess, where $G$ is a snowflake graph with center $r$. For a given $x\in [\rho ]$, let $\tilde{x}=\rho -x$. We construct the graph $G$ by creating a reduced caterpillar (see Definition 3) for each dome in $𝒟$ as follows.

• $\mathrm{■}$

  The reduced caterpillar of a singleton dome $(a,b)$ is a path of length $2\tilde{a}+2\tilde{b}$ with endpoints $p$ and $q$ (here, $p,q,z$ are special vertices in the reduced caterpillar, where $z$ is any arbitrary vertex).

• $\mathrm{■}$

  The reduced caterpillar of a regular dome $(a,b,c,d)$ is formed by a path of length $2\tilde{b}+2\tilde{d}+1$ with endpoints $p$ and $q$, which are two special vertices of the reduced caterpillar. The other special vertex $z$ of the reduced caterpillar is the vertex at distance $2\tilde{b}$ of $p$ (and thus distance $2\tilde{d}$ of $q$). In addition to the vertices on the path between $p$ and $q$, the reduced caterpillar includes $\tilde{a}-\tilde{b}$ (which equals $\tilde{c}-\tilde{d}$) other vertices which find $z$ as their sole neighbor.

For any reduced caterpillar $C$ constructed above (from either a singleton or a regular dome), we label the vertex at distances $\tilde{a}$ form $p$ as the first gate of $C$, denoted as $u$, and the one at distance $\tilde{b}$ from $q$ as the second gate of $C$ and denote it with $v$. We form the equivalent instance of the Telephone Broadguess problem by forming a graph $G$ with a center vertex $r$ (source) that is connected to all gates of all reduced caterpillars formed by the domes of $D$. By Definition 3, $G$ will be a snowflake graph with center $r$. Figure 5 provides an illustration of this reduction.

Before proving the correctness of our reduction, we prove the following lemmas for broadcasting in the reduced caterpillars associated with singleton and regular domes, respectively.

First, we show that if either (i) or (ii) hold, then broadcasting completes within $\rho$ rounds.

• $\mathrm{■}$

  Suppose (i) holds, that is, $u$ and $v$ are informed by times $b$ and $c$, respectively. We describe a broadcast scheme $S$ that completes within $\rho$ rounds. See Figure 6 for an illustration.

  In $S$, vertex $u$ first informs the neighbor on its path towards $p$, and then it informs the neighbors on its path towards $z$. This means that, by round $\rho$, all $\tilde{b}$ vertices on the path between $u$ and $p$ will be informed. Similarly, $\tilde{b}-1$ vertices on the path between $u$ and $z$ are informed (this excludes $z$). On the other hand, $v$ first informs the neighbor on its path towards $z$ and then the neighbor on its path towards $q$. This means that, by round $\rho$, all $\tilde{d}$ vertices on the path between $v$ and $q$ will be informed; this is because the number of rounds between the time that $v$ is informed and $\rho$ is $\tilde{c}$, and since $v$ first informs the neighbor towards $z$, $\tilde{c}-1$ rounds remain for informing vertices between $v$ and $q$. This number of rounds is sufficient because the length of the path between $v$ and $q$ is $\tilde{d}\le \tilde{c}-1$. This way, $z$ will receive the message at time $c+\tilde{d}$, and assuming $z$ informs its uninformed leaves in arbitrary order, the broadcasting in $S$ completes within $c+\tilde{d}+\tilde{c}-\tilde{d}=\rho$ rounds.

• $\mathrm{■}$

  Next, assume (ii) holds, that is, $u$ and $v$ are respectively informed by rounds $a$ and $d$. See Figure 6 for an illustration. In this case, $u$ first informs its neighbor on the path towards $z$ and then its other neighbor on the path towards $p$. This means that by round $a+\tilde{b}+1\le a+\tilde{a}=\rho$, all vertices on the path between $a$ and $p$ will be informed. Similarly, by round $a$, all the $\tilde{b}$ vertices on the path between $u$ and $z$ (including $z$) will be informed. Thus, all neighbors of $z$ will be informed by $a+\overline{b}+\overline{a}-\overline{b}=\rho$.

  On the other hand, $v$ first informs its neighbor on the path toward $q$ and then its neighbor on the path towards $z$ (excluding $z$). Thus, all vertices on the path between $v$ and $q$ will be informed by $d+\tilde{d}=\rho$ while vertices on the path between $v$ and $z$ (excluding $z$) will be informed by time $d+1-(\tilde{d}-1)=\rho$.

Next, assume that there is a broadcast scheme $S$ that completes within $\rho$ rounds. We want to show either (i) or (ii) holds. First, note that in the broadcast tree of $S$, vertices $u$ and $v$ cannot be in an ancestor-descendent relationship. Otherwise, if $u$ is an ancestor of $v$ (respectively $v$ is an ancestor of $u$), then $q$ (respectively $p$) receives the message no earlier than round $\tilde{b}+2\tilde{d}>\rho$ (respectively $2\tilde{b}+\tilde{d}>\rho$). Second, we note that $u$ (respectively $v$) cannot receive the message later than round $b$ (respectively $d$); otherwise $p$ (respectively $q$) will receive the message after round $\rho$. Moreover, since $z$ has $\tilde{a}-\tilde{b}$ (which equals $\tilde{c}-\tilde{d}$) neighbor that all are leaves, it must receive the message by round $\rho -(\tilde{a}-\tilde{b})=a+\tilde{b}$ (which equals $\rho -(\tilde{c}-\tilde{d})=c+\tilde{d}$) to complete broadcasting within $\rho$ rounds. This means that either $u$ is informed by round $a$ or $v$ is informed by round $c$ (otherwise, $z$ will be informed too late). We conclude that either (i) $u$ is informed by $a$ and $v$ is informed no later than $d$ or (ii) $u$ is informed by $b$ and $v$ is informed by $c$. $◀$

We are now ready to prove the main result of this section.

We use the construction mentioned in Section 4.3 to reduce any instance $𝒟=(D,m)$ of DoSePr to an instance $𝒯=(G,r,\rho )$. Note that each dome $D_i$ in $𝒟$ is bijected to a reduced caterpillar $C_i$ in $G$. The two possibilities for selecting an arc from a regular dome in $D_i$ translate to two possibilities for informing the gates of $C_i$.

Assume there is a valid solution $S$ for $𝒟$ in DoSePr. We will show there is a broadcasting scheme $S^{\prime }$ for $𝒯$ that completes within $\rho$ rounds. For that, we sort all endpoints of all arcs included in $S$ in non-decreasing order. Consider any dome $D_i\in D$, and let $e_1$ and $e_2$ be the endpoints of the arc selected from $D_i$ in $S$. Assume $e_1$ and $e_2$ have ranks $i_1$ and $i_2$ in the sorted order. In the broadcast scheme $S^{\prime }$, the source $r$ informs the gates of reduced caterpillar $C_i$ associated with $D_i$ at rounds $i_1$ and $i_2$. Given that the ranks of all arc endpoints in $S$ are distinct, $r$ informs at most one neighbor at each given round.

Next, we show that $S^{\prime }$ completes within round $\rho$. Given that $S$ is a valid solution for $𝒟$, for any $t\in m$, we have ${𝒩}_S(t)\le t$, where ${𝒩}_S(t)$ is the number of arc endpoints in $S$ that are at most $t$. On the other hand, for any $e$ that is the endpoint of an arc in $S$, we have $\text{rank}(e)\le {𝒩}_S(e)$ (be definition, $\text{rank}(e)$ is upper bounded by the number of arc endpoints in $S$ that are at most $e$, while ${𝒩}_S(e)$ is exactly the number of endpoints that are at most $e$). We conclude that $\text{rank}(e)\le e$. Therefore, the gates of any reduced caterpillar $C_i$ in $G$ associated with a singleton dome $D_i=(a,b)$ in $D$ receive the message in $S^{\prime }$ by rounds $(a,b)$. Similarly, the gates of any reduced caterpillar $C_i$ associated with a regular dome $D_i=(a,b,c,d)$ receive the message in $S^{\prime }$ by rounds $(a,d)$ (if the arc $(a,d)\in S$) or by rounds $(b,c)$ (if the arc $(b,c)$ is in $S$). Therefore, by Lemma 16 and 17, broadcasting in $S^{\prime }$ completes by round $\rho$.

For the other side of the reduction, suppose there is a broadcast scheme $S^{\prime }$ for $𝒯$ that completes within $\rho$ rounds. We will explain how to construct a valid solution $S$ for $𝒟$. Consider any reduced caterpillar $C_i$ in $G$ associated with a dome $D_i\in D$. Let $({\alpha }_i,{\beta }_i)$ be the rounds that center $r$ informs the gateways of $C_i$. Now, if $D_i=(a,b)$ is a singleton dome, by Lemma 16, it must be that the gates of $C_i$ are informed by rounds $(a,b)$, that is $\alpha \le a$ and $\beta \le b$. In this case, the single arc of $D_i$ is included in $S$. Next, if $D_i=(a,b,c,d)$ is a regular dome, by Lemma 17, it must be that the gates of $C_i$ are informed by either rounds $(a,d)$ or $(b,c)$, that is either ($\alpha \le a$ and $\beta \le d$) or ($\alpha \le b$ and $\beta \le c$) must hold. We will include arc $(a,d)$ in $S$ in the former case and $(b,c)$ in the latter case. In other words, any arc endpoint $x$ in $S$ is associated with a gate that is informed within round $x$ in $S^{\prime }$. To show that $S$ is a valid solution for $𝒟$, we show that for any $t\in [m]$, we have ${𝒩}_S(t)\le t$. Consider the set of endpoints in $D$ that contribute to ${𝒩}_S(t)$. As mentioned above, any of these endpoints is associated with a gate that is informed by $r$ within round $t$. Given that $r$ informs up to $t$ gates by round $t$, it must be that ${𝒩}_S(t)\le t$. We conclude that $S$ is a valid instance of $𝒟$.

One can verify that the size of the graph $G$ in the Telephone Broadguess instance is polynomial on $n=|D|$ and $m$. Therefore, given that the DoSePr is NP-hard by Lemma 15, we conclude that Telephone Broadguess is NP-hard. Telephone Broadcasting in general graphs is known to be in NP [28]. Together, these results establish that the NP-completeness of Telephone Broadguess in snowflake graphs. $◀$