在给定一个连通图 $G$ 和一个源点 $s \in V(G)$ 的情况下，如何确定所有顶点接收到仅由 $s$ 持有的消息所需的最小轮数？这个问题被称为电话广播，实际上是相当复杂的：在交汇于单一共享顶点的循环上仍然是 NP-hard，尤其是在路径宽度为2且线性反馈顶点集大小为1的图上，以及在树深度最多为6的图上 [Egami et al.; MFCS '25]。
在一些参数下，如顶点覆盖数、顶点完整性和到 clique 的距离，电话广播是固定参数可处理的。对于顶点覆盖数 $\text{vc}$，存在一个运行时间为 $2^{\text{O}(\text{vc}^3)} n^{\text{O}(1)}$ 的算法 [Fomin, Fraigniaud, Golovach; TCS '24]，一个基于顶点完整性 $\text{vi}$ 的双指数算法，以及一个基于到 clique 距离 $k$ 的运行时间为 $2^{\text{O}(k^2)} n^{\text{O}(1)}$ 的算法 [Egami et al.; MFCS '25]。
在本文中，我们提出了改进的电话广播参数化算法，其运行时间为 $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)}$ 和 $2^{\text{O}(k \log k)} n^{\text{O}(1)}$。我们算法的主要加速成分是对边加权 $b$-匹配的图灵约简。
博主点评： 本文提出的改进算法显著提升了电话广播的效率，尤其在复杂图结构中表现突出，展示了参数化算法在解决 NP-hard 问题中的潜力。通过引入边加权 $b$-匹配的图灵约简，算法的运行时间得到了有效压缩，值得在实际应用中进一步探索。