{"ID":5675172,"CreatedAt":"2026-07-03T01:40:09.565152011Z","UpdatedAt":"2026-07-05T06:33:48.009886606Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01770","arxiv_id":"2607.01770","title":"Faster Parameterized Broadcasting","abstract":"Given a connected graph $G$ and a source $s \\in V(G)$, what is the smallest number of rounds necessary for all vertices of $G$ to receive a message initially only held by $s$, where at each round every informed vertex passes the message to one of its neighbors? This problem is called Telephone Broadcast and is suprisingly hard: it remains NP-hard on cycles intersecting at a single shared vertex, in particular, graphs of pathwidth 2 with a linear feedback vertex set of size 1, as well as on graphs with treedepth at most 6 [Egami et al.; MFCS '25]. Vertex cover number, vertex integrity, and distance to clique are among the few parameters for which Telephone Broadcast is fixed-parameter tractable. There is a $2^{\\mathcal{O}(\\mathrm{vc}^3)} n^{\\mathcal{O}(1)}$-time algorithm parameterized by vertex cover number $\\mathrm{vc}$ [Fomin, Fraigniaud, Golovach; TCS '24], a double-exponential algorithm parameterized by vertex integrity $\\mathrm{vi}$, and a $2^{\\mathcal{O}(k^2)} n^{\\mathcal{O}(1)}$-time algorithm parameterized by distance to clique $k$ [Egami et al.; MFCS '25]. In this paper, we give improved parameterized algorithms for Telephone Broadcast with running times $2^{\\mathcal{O}(\\mathrm{vc} \\log \\mathrm{vc})} n^{\\mathcal{O}(1)}$, $2^{\\mathcal{O}(\\mathrm{vi}^2 \\log \\mathrm{vi})} n^{\\mathcal{O}(1)}$, and $2^{\\mathcal{O}(k \\log k)} n^{\\mathcal{O}(1)}$. The main ingredient that makes our algorithms faster is a Turing reduction to edge-weighted $b$-Matching.","short_abstract":"Given a connected graph $G$ and a source $s \\in V(G)$, what is the smallest number of rounds necessary for all vertices of $G$ to receive a message initially only held by $s$, where at each round every informed vertex passes the message to one of its neighbors? This problem is called Telephone Broadcast and is suprisin...","url_abs":"https://arxiv.org/abs/2607.01770","url_pdf":"https://arxiv.org/pdf/2607.01770v1","authors":"[\"Édouard Bonnet\",\"Carl Feghali\",\"Manolis Vasilakis\"]","published":"2026-07-02T06:42:14Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}