Given a connected graph $G$ and a source $s \in V(G)$, how can we determine the smallest number of rounds necessary for all vertices to receive a message initially held by $s$? This problem, termed Telephone Broadcast, is surprisingly complex: it remains NP-hard on cycles intersecting at a single shared vertex, particularly in graphs with pathwidth 2 and a linear feedback vertex set of size 1, as well as on graphs with treedepth at most 6 [Egami et al.; MFCS '25].
The Telephone Broadcast problem is fixed-parameter tractable for parameters like vertex cover number, vertex integrity, and distance to clique. For vertex cover number $\text{vc}$, there is a $2^{\text{O}(\text{vc}^3)} n^{\text{O}(1)}$-time algorithm [Fomin, Fraigniaud, Golovach; TCS '24], a double-exponential algorithm parameterized by vertex integrity $\text{vi}$, and a $2^{\text{O}(k^2)} n^{\text{O}(1)}$-time algorithm parameterized by distance to clique $k$ [Egami et al.; MFCS '25].
In this paper, we present improved parameterized algorithms for Telephone Broadcast with running times of $2^{\text{O}(\text{vc} \log \text{vc})} n^{\text{O}(1)}$, $2^{\text{O}(\text{vi}^2 \log \text{vi})} n^{\text{O}(1)}$, and $2^{\text{O}(k \log k)} n^{\text{O}(1)}$. The key to our faster algorithms is a Turing reduction to edge-weighted $b$-Matching.
Blogger's Review: The improved algorithms presented in this paper significantly enhance the efficiency of Telephone Broadcast, particularly in complex graph structures, showcasing the potential of parameterized algorithms in addressing NP-hard problems. The incorporation of Turing reduction to edge-weighted $b$-Matching effectively compresses the running time and merits further exploration in practical applications.