Broadcasting in graphs refers to the information dissemination problem in which a source node has an atomic piece of information to be distributed to all the nodes of a graph. In the standard telephone model, broadcasting proceeds as a sequence of synchronous rounds, where, at each round, every informed node can transfer the information to at most one of its neighbors. The broadcast time of a graph $G$ is the maximum, taken over every node $v\in V(G)$, of the minimum number of rounds required for broadcasting from $v$ in $G$. We study the network design problem that, for every $\epsilon>0$, asks for the minimum number of edges of $n$-node graphs with broadcast time close to optimal, i.e., at most $(1+\epsilon)\log_2n$. Let $\phi=(1+\sqrt{5})/2$ be the golden ratio, and let $\alpha=1/\log_2\phi-1\simeq 0.44$. We show that, for every $n\geq 1$, and for every $\epsilon\in(0,\alpha)$, it suffices to add $O(n^{1-\epsilon/\alpha})$ edges to a well chosen $n$-node tree for designing an $n$-node graph with broadcast time $(1+\epsilon)\log_2n$. This asymptotic bound on the additional number of edges improves the previsouly known bound $O(n^{1-\epsilon})$, and has implications to the design of graphs with minimum broadcast cost, defined as number of edges times broadcast time. Moreover, we show that, for infinitely many values of $n$, $\Omega(n)$ edges must be added to some tree for designing an $n$-node graph with broadcast time $\lceil\log_2 n\rceil+1$. Therefore, our bound $O(n^{1-\epsilon/\alpha})$ on the additional number of edges for $0<\epsilon<\alpha$ is asymptotically tight at the two extremities of the interval $(0,\alpha]$, as it is $O(n)$ when $\epsilon\to 0$, and $O(1)$ when $\epsilon=\alpha$. Finally, we show that, for every $n$, there exists an $n$-node graph with broadcast time $\lceil\log_2 n\rceil+1$ and at most $2n-4\lceil\log_2n\rceil+O(1)$ edges.
Pierre Fraigniaud, Hovhannes A. Harutyunyan· 0 citations
We show that the complexity gaps in the round complexities of locally checkable labeling (LCL) problems are not due to the fact that solutions to LCL problems must be locally checkable, but solely to the fact that LCL problems are defined only for graphs of maximum degree upper bounded by some arbitrary yet constant value $\Delta$. Specifically, we show that there are infinitely many locally checkable problems (i.e., problems whose solutions can be checked locally) whose round complexities belongs to the two intervals $[\omega(1),o(\log\log^\star n)]$ and $[\omega(\log^\star n),o(\log n)]$ whenever these problems are considered in networks with unbounded maximum degrees. This extends the previous results by Schmid (arXiv, 2026), which hold for the polynomial regime only, and by Bousquet, Feuilloley, and Pierron (OPODIS, 2025), which hold for trees only. All our upper bounds are obtained using deterministic algorithms that can be run under the port-numbering model, which is a weak variant of LOCAL, without any a priori information on the number of nodes in the network. Instead, our lower bounds apply to randomized LOCAL, and quantum LOCAL, even if nodes have identifiers in $[1,n]$, and even if they know the exact number of nodes in the network. They even hold under randomized online LOCAL, a strong variant of the LOCAL model. Finally, our lower bounds hold even for trees. Our results are obtained using two main ingredients. The first one is the analysis of a new locally checkable problem called Increasing Degree, parameterized by a function $f:\mathbb{N}\to\mathbb{N}$. Different round complexities can be obtained by tuning the function $f$ accordingly. Our second tool is a general Translation Theorem that enables to transfer results from a given range of complexities to results for a range of lower complexities.
Filippo Casagrande, Pierre Fraigniaud, Benjamín Jauregui et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
