Exploiting Graph Structure for Near-Optimal Broadcasting

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.