← 研踪 PaperTrailarXiv:2610.27422 · v2
Approximation Algorithms for Directed Telephone Multicast
首次提交 2026-10-20 08:18
版本更新 2026-11-03 20:21
雷达观测 2026-11-04 23:39
摘要
Telephone multicast is a classical problem in information dissemination. In the directed setting, a message starts at a source in an $n$-vertex digraph, and each informed vertex may call one out-neighbour per round. The goal is to inform a given set of $k$ terminals in the fewest rounds. Despite previous work on telephone multicast, a substantial approximation gap remained in the directed setting: approximating the problem within a factor of $o(\log k)$ is NP-hard, while the best existing polynomial-time approximation guarantee depending only on $k$ was $\widetilde O(\sqrt{k})$. For every integer $\ell\ge2$, we give a deterministic combinatorial algorithm that runs in $n^{O(\ell)}$ time and returns a schedule of length $O(\ell^3\log k)(OPT+k^{1/\ell})$, where $OPT$ is the optimum number of rounds. This yields an $O(k^ε)$ approximation in time $n^{O(1/ε)}$ for every fixed $ε>0$, and an $O(\log^4 k)$ approximation in quasi-polynomial time. The same algorithm gives an $O(\log k)$ approximation whenever $OPT\ge k^ε$ for a fixed $ε\in(0,1)$, which is optimal up to a constant factor unless $\mathrm{P}=\mathrm{NP}$. On planar digraphs, we obtain a deterministic polynomial-time $O(\log^2 k)$ approximation. More generally, we give an $O(p\log^2 k)$ approximation for minor-closed graph classes with the following separator property. Given any rooted spanning tree, a balanced separator can be computed in polynomial time as the union of all vertices on at most $p$ tree paths from the root to chosen vertices. Classes of bounded treewidth satisfy this property. We also strengthen the known logarithmic approximation hardness for directed telephone multicast, extending it from instances with a polynomially large optimum to instances with $OPT=O(\log k)$.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-03 20:21 · 最新观测版本
Approximation Algorithms for Directed Telephone Multicast
Telephone multicast is a classical problem in information dissemination. In the directed setting, a message starts at a source in an $n$-vertex digraph, and each informed vertex may call one out-neighbour per round. The goal is to inform a given set of $k$ terminals in the fewest rounds. Despite previous work on telephone multicast, a substantial approximation gap remained in the directed setting: approximating the problem within a factor of $o(\log k)$ is NP-hard, while the best existing polynomial-time approximation guarantee depending only on $k$ was $\widetilde O(\sqrt{k})$. For every integer $\ell\ge2$, we give a deterministic combinatorial algorithm that runs in $n^{O(\ell)}$ time and returns a schedule of length $O(\ell^3\log k)(OPT+k^{1/\ell})$, where $OPT$ is the optimum number of rounds. This yields an $O(k^ε)$ approximation in time $n^{O(1/ε)}$ for every fixed $ε>0$, and an $O(\log^4 k)$ approximation in quasi-polynomial time. The same algorithm gives an $O(\log k)$ approximation whenever $OPT\ge k^ε$ for a fixed $ε\in(0,1)$, which is optimal up to a constant factor unless $\mathrm{P}=\mathrm{NP}$. On planar digraphs, we obtain a deterministic polynomial-time $O(\log^2 k)$ approximation. More generally, we give an $O(p\log^2 k)$ approximation for minor-closed graph classes with the following separator property. Given any rooted spanning tree, a balanced separator can be computed in polynomial time as the union of all vertices on at most $p$ tree paths from the root to chosen vertices. Classes of bounded treewidth satisfy this property. We also strengthen the known logarithmic approximation hardness for directed telephone multicast, extending it from instances with a polynomially large optimum to instances with $OPT=O(\log k)$.
查看此版本解读 →查看此版本原文 ↗