Exploiting Graph Structure for Near-Optimal Broadcasting
2026-07-15 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how information spreads in networks where each informed person can tell only one uninformed neighbor at a time. They focus on creating faster approximation algorithms that give valid schedules for informing everyone, improving previous exact methods. They provide new algorithms for special kinds of graphs and show that some related problems are likely too hard for the best-known exact approaches. Their work balances between exact solutions and practical approximations for spreading information efficiently.
Telephone broadcastingBroadcasting problemApproximation algorithmsFPT algorithmsVertex integrityParameterized complexityDistance-to-cliqueDistance-to-pathDominating setGraph diameter
Authors
Rudranarayan Kar, Praneet Kumar Patra, Diya Roy, Abhishek Sahu
Abstract
Telephone broadcasting is a classical model for spreading information in a network. Given a connected graph $G(V,E)$ with source vertex $s$, each informed vertex may inform exactly one uninformed neighbor in every time step. The \textsc{Broadcasting} problem asks whether all vertices can be informed within $t$ steps; the minimum such value is the broadcast time $b(G,s)$. A related variant considers the worst-case source, $b(G)=\max_{u\in V} b(G,u)$. Both variants are NP-hard, and every $n$-vertex graph satisfies $b(G,s)\ge \log_2 n$. Fomin \textit{et al.}~\cite{fomin2023parameterized} recently gave FPT algorithms for this problem under several structural graph parameters. Instead of computing optimal broadcast schedules, we study faster approximation algorithms that produce valid schedules. We improve the $O^*(3^n)$ exact algorithm of Fomin \textit{et al.} to an $O^*((3-f(x))^n)$ algorithm with a $+x$ additive approximation, where $f(x)>0$ is a constant for every fixed $x$. We also give approximation algorithms on graphs of bounded vertex integrity, including a polynomial-time $+2k$ additive approximation algorithm. Complementing these positive results, we prove parameterized hardness for vertex cover above maximum matching ($\mathrm{VC}-\mathrm{MM}$), dominating set size, and graph diameter, indicating that FPT algorithms for these parameters are unlikely. Finally, we present a $+2$ additive approximation algorithm for distance-to-clique running in $O^*(2^{O(k\log k)})$ time, a $2$-factor approximation algorithm for distance-to-path running in XP time, and a polynomial-time algorithm for polar graphs.