pith. sign in

arxiv: 2410.01048 · v2 · submitted 2024-10-01 · 💻 cs.DS

The Telephone k-Multicast Problem

Daniel Hathcock , Guy Kortsarz , R. Ravi This is my paper

Pith reviewed 2026-05-23 19:52 UTC · model grok-4.3

classification 💻 cs.DS
keywords telephone multicastk-multicastapproximation algorithmspoisenetwork decompositiondirected Steiner treepartition matroidbounded treewidth
0
0 comments X

The pith

The telephone k-multicast problem admits an Õ(t^{1/3}) multiplicative approximation in undirected graphs and an additive Õ(k^{1/2}) approximation in directed graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops approximation algorithms for minimum-time multicasting in the telephone model, where a message spreads from a root to terminals via matchings in each round. It focuses on the k-multicast variant that requires informing only k out of t terminals, providing a multiplicative Õ(t^{1/3}) approximation for undirected graphs. For directed graphs, it achieves an additive Õ(k^{1/2}) approximation with a polylog multiplicative factor. These results come from reducing the multicast problem to minimum-poise k-tree problems and solving those with greedy network decomposition and set covering under partition matroid constraints. The approach also yields improved polylogarithmic approximations for bounded-degree Directed Steiner Tree on bounded-treewidth graphs.

Core claim

The central claim is that by reducing telephone k-multicast to the minimum-poise k-tree problem, and applying greedy network decomposition plus set-covering under partition matroid constraints, one obtains a multiplicative Õ(t^{1/3}) approximation for the undirected case and an additive Õ(k^{1/2}) approximation for the directed case.

What carries the argument

Reduction of telephone k-multicast to minimum-poise k-tree problems, solved via greedy network decomposition and set covering under partition matroid constraints.

If this is right

  • The undirected k-multicast can be approximated multiplicatively by Õ(t^{1/3}).
  • Directed k-multicast admits an additive Õ(k^{1/2}) approximation.
  • Bounded-degree directed Steiner trees on bounded-treewidth graphs have improved polylog approximations.
  • These techniques extend prior work on group Steiner trees.
  • Partial multicasting serves as an intermediate problem between full multicast and Steiner tree problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the poise reduction holds tightly, it may suggest similar reductions for other dissemination problems in networks.
  • Testing the algorithms on random graphs or real-world communication networks could reveal practical performance beyond the worst-case bounds.
  • Extending the bounded-treewidth result to other graph classes might improve approximations for Steiner problems in planar or minor-free graphs.
  • The additive approximation in directed graphs could lead to better heuristics for multicast in asymmetric networks.

Load-bearing premise

The reduction from the telephone k-multicast problem to minimum-poise k-tree problems preserves the approximation factors claimed.

What would settle it

Finding a family of graphs where the minimum time to inform k terminals is much larger than the poise of the best k-tree would falsify the reduction's utility for approximation.

Figures

Figures reproduced from arXiv: 2410.01048 by Daniel Hathcock, Guy Kortsarz, R. Ravi.

Figure 1
Figure 1. Figure 1: A depiction of the algorithm in the case that a [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
read the original abstract

We consider minimum time multicasting problems in directed and undirected graphs: given a root node and a subset of $t$ terminal nodes, multicasting seeks to find the minimum number of rounds within which all terminals can be informed with a message originating at the root. In each round, the telephone model we study allows the information to move via a matching from the informed nodes to the uninformed nodes. Since minimum time multicasting in digraphs is poorly understood compared to the undirected variant, we study an intermediate problem in undirected graphs that specifies a target $k < t$, and requires that only $k$ of the terminals be informed in the minimum number of rounds. For this problem, we improve the implications of the previous results and obtain a multiplicative approximation factor of $\tilde{O}(t^{1/3})$. For the directed version, we obtain an additive $\tilde{O}(k^{1/2})$ approximation algorithm (with a polylogarithmic multiplicative factor). Our algorithms are based on reductions to the related problems of finding $k$-trees of minimum poise (sum of maximum degree and diameter) and applying a combination of greedy network decomposition techniques and set covering under partition matroid constraints. We also study the problem of bounded degree Directed Steiner Tree, for which we obtain improved polylogarithmic approximations for the special case of bounded treewidth graphs. This extends prior work on the Group Steiner Tree problem.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 4 minor

Summary. The paper studies the telephone k-multicast problem (minimum rounds to inform k out of t terminals from a root under the telephone matching model) in undirected and directed graphs. It claims an Õ(t^{1/3}) multiplicative approximation for the undirected case and an additive Õ(k^{1/2}) approximation (with polylog multiplicative factor) for the directed case, obtained via reduction to minimum-poise k-tree followed by greedy network decomposition and set-covering under partition matroid constraints. It also gives improved polylog approximations for bounded-degree Directed Steiner Tree on bounded-treewidth graphs.

Significance. If the claimed approximation factors hold, the results meaningfully advance the state of knowledge on telephone multicasting, particularly by handling the directed case (previously poorly understood) and improving the k-version in undirected graphs. The reduction-based approach and use of standard primitives (network decomposition, matroid-constrained set cover) are appropriate; the bounded-treewidth Steiner Tree extension is a useful side contribution. No machine-checked proofs or reproducible artifacts are mentioned.

minor comments (4)
  1. The abstract states that the algorithms 'improve the implications of the previous results' for undirected k-multicast but does not name the prior approximation factors or cite the specific earlier papers; adding a short comparison paragraph in §1 would clarify the improvement.
  2. In the directed case the claimed additive Õ(k^{1/2}) bound includes an unspecified polylog multiplicative factor; stating the precise polylog degree (e.g., O(log^2 n) or similar) in the theorem statement would strengthen the result.
  3. The reduction from telephone k-multicast to min-poise k-tree is central; a brief sketch of how the poise objective maps back to the multicast time (including any hidden constants or log factors) in the main theorem would aid readability.
  4. Figure captions and table headers use inconsistent notation for the parameters t, k, and n; standardizing them (e.g., always writing t for number of terminals) would improve clarity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the paper and recommendation for minor revision. The report does not list any specific major comments requiring point-by-point response.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's derivation consists of a reduction from telephone k-multicast to minimum-poise k-tree, followed by greedy network decomposition and set-covering under partition matroid constraints. These are standard algorithmic primitives whose approximation guarantees are derived from independent analysis (e.g., greedy set cover bounds and matroid properties) rather than any quantity defined in terms of the target approximation factor itself. No equations, fitted parameters, self-definitional steps, or load-bearing self-citations appear in the provided text that would reduce the claimed Õ(t^{1/3}) or Õ(k^{1/2}) factors to tautologies. The result is self-contained against external verification of the cited techniques.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Review performed from abstract alone; no explicit free parameters, invented entities, or non-standard axioms are stated. The work relies on standard graph-theoretic assumptions (existence of matchings, tree decompositions) that are treated as background.

axioms (2)
  • standard math Standard facts about matchings, diameters, and degrees in undirected and directed graphs hold.
    Invoked implicitly when defining the telephone model and poise.
  • standard math Partition matroids admit efficient greedy set-cover approximations.
    Used in the covering step; this is a known algorithmic fact.

pith-pipeline@v0.9.0 · 5784 in / 1455 out tokens · 31298 ms · 2026-05-23T19:52:08.952406+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Maximizing a monotone submodular function subject to a matroid constraint

    Gruia C a linescu, Chandra Chekuri, Martin P \' a l, and Jan Vondr \' a k. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. , 40(6):1740--1766, 2011

    work page 2011

  2. [2]

    Demers, Daniel H

    Alan J. Demers, Daniel H. Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard E. Sturgis, Daniel C. Swinehart, and Douglas B. Terry. Epidemic algorithms for replicated database maintenance. In Fred B. Schneider, editor, Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, Vancouver, British Columbia, Canada,...

    work page 1987

  3. [3]

    A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem

    Michael Elkin and Guy Kortsarz. A combinatorial logarithmic approximation algorithm for the directed telephone broadcast problem. SIAM J. Comput. , 35(3):672--689, 2005

    work page 2005

  4. [4]

    Elkin and G

    M. Elkin and G. Kortsarz. An approximation algorithm for the directed telephone multicast problem. Algorithmica , 45(4):569--583, 2006

    work page 2006

  5. [5]

    Sublogarithmic approximation for telephone multicast

    Michael Elkin and Guy Kortsarz. Sublogarithmic approximation for telephone multicast. J. Comput. Syst. Sci. , 72(4):648--659, 2006

    work page 2006

  6. [6]

    M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. An analysis of approximations for maximizing submodular set functions---II , pages 73--87. Springer Berlin Heidelberg, Berlin, Heidelberg, 1978

    work page 1978

  7. [7]

    Ganesan, B

    D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, and S. Wicker. Complex behavior at scale: An experimental study of low-power wireless sensor networks. Technical report, UCLA/CSD-TR 02 , 2002

    work page 2002

  8. [8]

    Hedetniemi, Stephen T

    Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Arthur L. Liestman. A survey of gossiping and broadcasting in communication networks. Networks , pages 319--349, 1988

    work page 1988

  9. [9]

    Impagliazzo and R

    R. Impagliazzo and R. Paturi. On the complexity of k-sat. J. Comput. Syst. Sci. , 62(2):367--375, 2001

    work page 2001

  10. [10]

    On some network design problems with degree constraints

    Rohit Khandekar, Guy Kortsarz, and Zeev Nutov. On some network design problems with degree constraints. J. Comput. Syst. Sci. , 79(5):725--736, 2013

    work page 2013

  11. [11]

    The structure of information pathways in a social communication network

    Gueorgi Kossinets, Jon Kleinberg, and Duncan Watts. The structure of information pathways in a social communication network. In Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining , pages 435--443, 2008

    work page 2008

  12. [12]

    The minimum degree group steiner problem

    Guy Kortsarz and Zeev Nutov. The minimum degree group steiner problem. Discret. Appl. Math. , 309:229--239, 2022

    work page 2022

  13. [13]

    D. R. Kowalski and A. Pelc. Optimal deterministic broadcasting in known topology radio networks. Distributed Comput. , 19(3):185--195, 2007

    work page 2007

  14. [14]

    Afshin Nikzad and R. Ravi. Sending secrets swiftly: Approximation algorithms for generalized multicast problems. In ICALP , pages 568--607, 2014

    work page 2014

  15. [15]

    Melih Onus and Andr \' e a W. Richa. Minimum maximum-degree publish-subscribe overlay network design. IEEE/ACM Trans. Netw. , 19(5):1331--1343, 2011

    work page 2011

  16. [16]

    Distributed Computing: A Locality-Sensitive Approach

    David Peleg. Distributed Computing: A Locality-Sensitive Approach . Society for Industrial and Applied Mathematics, 2000

    work page 2000

  17. [17]

    Timeliness through telephones: Approximating information freshness in vector clock models

    Da Qi Chen, Lin An, Aidin Niaparast, R Ravi, and Oleksandr Rudenko. Timeliness through telephones: Approximating information freshness in vector clock models. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages 2411--2428. SIAM, 2023

    work page 2023

  18. [18]

    R. Ravi. Rapid rumor ramification: Approximating the minimum broadcast time (extended abstract). In 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994 , pages 202--213. IEEE Computer Society, 1994

    work page 1994