pith. sign in

arxiv: 2509.26426 · v2 · submitted 2025-09-30 · 💻 cs.DS

A Linear-Time 1.5-Approximation for Broadcasting in k-Cycle Graphs

Jeffrey Bringolf , Anne-Laure Ehresmann , Hovhannes A. Harutyunyan This is my paper

Pith reviewed 2026-05-18 11:58 UTC · model grok-4.3

classification 💻 cs.DS
keywords broadcastingapproximation algorithmk-cycle graphsflower graphslinear timecactus graphsnetwork disseminationinformation dissemination
0
0 comments X

The pith

A linear-time algorithm approximates broadcast time in k-cycle graphs to within 1.5 minus a structure-dependent epsilon.

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

The paper establishes a straightforward algorithm that approximates the minimum time for a message to reach every node starting from any originator in a k-cycle graph. This family, also known as flower graphs, is a highly restricted class of cactus graphs where computing exact broadcast time remains NP-hard. The method runs in linear time by directly using the graph's cycle-sharing structure rather than searching over all possible dissemination orders. A factor of 1.5 minus a positive epsilon that depends on the specific cycles and attachments is guaranteed. This provides a practical way to estimate dissemination performance in networks with this topology without solving the full hard problem.

Core claim

For networks whose topology is a k-cycle graph, the broadcast time of any node can be approximated within a multiplicative factor of 1.5 minus a positive epsilon by a direct linear-time procedure that inspects the cycles attached at the common vertex and selects dissemination paths accordingly.

What carries the argument

The k-cycle graph structure, consisting of multiple cycles that all share exactly one common vertex, which permits a direct linear scan to select near-optimal broadcast schedules without enumeration.

If this is right

  • Exact computation can be replaced by this fast approximation when the network is known to be a k-cycle graph.
  • Large instances of such networks can have their broadcast performance estimated without exponential runtime.
  • Network design choices that produce flower-like topologies can be evaluated quickly for information dissemination speed.
  • The epsilon improvement over 1.5 can be computed directly from the cycle lengths and attachments in the given graph.

Where Pith is reading between the lines

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

  • The same structural simplification might extend to other cactus subfamilies that were previously shown hard, potentially yielding approximation algorithms there as well.
  • The linear-time method could serve as a fast subroutine inside heuristics for broadcasting on arbitrary graphs that contain identifiable k-cycle substructures.
  • Empirical tests on generated k-cycle graphs with varying numbers of cycles could reveal how often the achieved ratio is strictly better than 1.5.

Load-bearing premise

The input graph must belong to the k-cycle family and possess the cycle-attachment properties that allow the approximation ratio to be achieved by a single linear pass without any hidden search steps.

What would settle it

A specific k-cycle graph together with an originator where the algorithm's reported broadcast time exceeds 1.5 minus epsilon times the true minimum broadcast time that can be verified by exhaustive enumeration on that small instance.

Figures

Figures reproduced from arXiv: 2509.26426 by Anne-Laure Ehresmann, Hovhannes A. Harutyunyan, Jeffrey Bringolf.

Figure 1
Figure 1. Figure 1: An example of a snowflake graph. A snowflake graph consists of a k-cycle graph with paths originating from the vertices adjacent to the central vertex. One vertex on each cycle can also have any number of additional adjacent vertices. Snowflake graphs are cactus graphs with pathwidth at most 2 [1]. Recently, Egami et al. proved that the broadcast time problem is NP-complete in cactus graphs that are distan… view at source ↗
Figure 2
Figure 2. Figure 2: An example of a graph created by the reduction in [8]. The graph consists of a k-cycle graph with paths connected to the central vertex. The aforementioned findings regarding the NP-hardness of highly restricted families of cactus graphs raise the question of whether the broadcast time prob￾lem is also NP-hard for the next logical subfamily—k-cycle graphs. In fact, we are currently preparing a manuscript i… view at source ↗
Figure 3
Figure 3. Figure 3: An example of a k-cycle graph with k = 5 and l1 = 7, l2 = 5, l3 = 5, l4 = 4, l5 = 2. We assume that cycles are indexed in non-increasing order of their lengths. Formally, l1 ≥ l2 ≥ ... ≥ lk ≥ 2, where li is the number of vertices on cycle Ci (excluding vc) for all 1 ≤ i ≤ k. As noted above, the broadcast time problem has been researched at length for cactus graphs and graphs with pathwidth at most 2 in [1]… view at source ↗
Figure 4
Figure 4. Figure 4: An example of a broadcast scheme generated by Simple-K-Cycle on a k-cycle graph with l1 = 6, l2 = 5, l3 = 2 and originator vc. vc calls cycle C1 in time units 1 and 4, cycle C2 in time units 2 and 5, and cycle C3 in time unit 3. The broadcast is completed in 5 time units. Theorem 1. Algorithm 1 is a polynomial-time (1.5 − ϵ)-approximation algo￾rithm for general k-cycle graphs when the originator is vc. Pro… view at source ↗
Figure 5
Figure 5. Figure 5: An example of a broadcast scheme generated by Simple-K-Cycle on a k-cycle graph with l1 = 9, l2 = 8, l3 = 4, l4 = 2 and originator u with dist(u, vc) = d = 2. u informs towards vc in time unit 1, then informs its other neighbour in time unit 2. vc is informed in time unit 2. Then, vc calls cycle C1 in time units 3 and 6, cycle C2 in time unit 7, cycle C3 in time units 4 and 8, and cycle C4 in time unit 5. … view at source ↗
read the original abstract

Broadcasting is an information dissemination primitive where a message originates at a node (called the originator) and is passed to all other nodes in the network. Broadcasting research is motivated by efficient network design and determining the broadcast times of standard network topologies. Verifying the broadcast time of a node $v$ in an arbitrary network $G$ is known to be NP-hard. Additionally, recent findings show that the broadcast time problem is NP-hard in several highly restricted subfamilies of cactus graphs. The most restrictive of these families is known as \emph{$k$-cycle graphs} or \emph{flower graphs} and is the focus of this paper. We present a simple $(1.5-\epsilon)$-approximation algorithm for determining the broadcast time of networks modeled using $k$-cycle graphs, where $\epsilon > 0$ depends on the structure of the graph.

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

2 major / 2 minor

Summary. The manuscript claims to present a simple (1.5−ε)-approximation algorithm for determining the broadcast time of networks modeled as k-cycle graphs (flower graphs), where ε > 0 depends on the graph structure. It notes the NP-hardness of the broadcast time problem in general networks and in broader cactus subfamilies, then restricts attention to this family to obtain the claimed linear-time approximation.

Significance. If the central claims hold, the result would supply an efficient approximation procedure for broadcast times in a restricted but natural family of graphs consisting of multiple cycles sharing a single vertex. The linear-time guarantee would be valuable for large instances provided it is independent of k, and the (1.5−ε) ratio offers a concrete improvement over trivial bounds. The work would thereby contribute a positive algorithmic result for a topology where exact solution remains hard in wider cactus classes.

major comments (2)
  1. [Abstract and §1] Abstract and §1: the abstract asserts the existence of a (1.5−ε) approximation and linear runtime but supplies no proof sketch, pseudocode, or analysis of the approximation ratio. This leaves the central claim without visible derivation or verification steps.
  2. [§4 (Runtime Analysis)] §4 (Runtime Analysis): the linear-time claim may hide exponential dependence on k in the DP or enumeration steps over cycles. The algorithm's correctness and linear-time guarantee rest on the specific structural properties of k-cycle graphs that permit a simple approximation without post-hoc adjustments or hidden exponential steps; if the algorithm processes combinations of the k cycles or solves subproblems per cycle with state exponential in k, this would incur factors like O(k·2^k) or worse, contradicting the title and abstract while still permitting a correct but slower approximation.
minor comments (2)
  1. [Introduction] Introduction: the notation for k-cycle graphs and the precise definition of ε could be introduced with a small illustrative figure or formal definition to improve readability.
  2. [References] References: ensure citations to prior NP-hardness results on cactus graphs are complete and up-to-date.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the positive assessment of its potential significance. We respond to each major comment below.

read point-by-point responses

  1. Referee: [Abstract and §1] Abstract and §1: the abstract asserts the existence of a (1.5−ε) approximation and linear runtime but supplies no proof sketch, pseudocode, or analysis of the approximation ratio. This leaves the central claim without visible derivation or verification steps.

    Authors: The abstract is kept concise to emphasize the primary result. The complete algorithm description, pseudocode, correctness proof, and approximation-ratio analysis appear in Sections 2–4. To improve accessibility, we will expand the abstract with a brief outline of the algorithmic approach and the key steps in the ratio analysis. revision: yes

  2. Referee: [§4 (Runtime Analysis)] §4 (Runtime Analysis): the linear-time claim may hide exponential dependence on k in the DP or enumeration steps over cycles. The algorithm's correctness and linear-time guarantee rest on the specific structural properties of k-cycle graphs that permit a simple approximation without post-hoc adjustments or hidden exponential steps; if the algorithm processes combinations of the k cycles or solves subproblems per cycle with state exponential in k, this would incur factors like O(k·2^k) or worse, contradicting the title and abstract while still permitting a correct but slower approximation.

    Authors: The algorithm exploits the flower-graph structure by processing each cycle independently after a single linear-time traversal of the shared vertex. No subset enumeration or DP table whose size grows with k is used; decisions per cycle are made in constant time relative to cycle length. Consequently the total running time is strictly linear in the number of vertices n (with k absorbed into the input size). We will insert an explicit sentence in §4 confirming the absence of any exponential dependence on k. revision: partial

Circularity Check

0 steps flagged

No circularity: algorithmic construction is self-contained

full rationale

The paper presents a new (1.5-ε)-approximation algorithm for broadcast time restricted to k-cycle graphs, framed explicitly as a direct algorithmic construction that exploits the specific structure of these graphs to achieve linear time. No equations, parameter fitting, self-definitional steps, or load-bearing self-citations appear in the provided abstract or description. The central claim does not reduce to prior inputs by construction; it is an independent algorithmic result whose correctness rests on graph-theoretic properties rather than any fitted quantity or renamed prior result. This is the expected honest outcome for a constructive algorithmic paper.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The contribution relies on standard definitions of broadcasting and the structural definition of k-cycle graphs. No free parameters, new entities, or ad-hoc axioms are visible in the abstract.

axioms (2)
  • standard math Broadcasting is defined as a message originating at one node and propagating to all others along edges.
    This is the standard model invoked when the paper discusses broadcast time.
  • domain assumption k-cycle graphs form a well-defined restricted subclass of cactus graphs.
    The paper focuses on this family after referencing NP-hardness in broader subfamilies.

pith-pipeline@v0.9.0 · 5689 in / 1308 out tokens · 34235 ms · 2026-05-18T11:58:03.691514+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

28 extracted references · 28 canonical work pages

  1. [1]

    Aminian, A., Kamali, S., Seyed-Javadi, S.M., Sumedha: On the complexity of telephone broadcasting: From cacti to bounded pathwidth graphs (2025),https: //arxiv.org/abs/2501.12316, to appear in Proceedings of ICALP 2025

    work page arXiv 2025

  2. [2]

    SIAM Journal on Computing30(2), 347–358 (2000)

    Bar-Noy, A., Guha, S., Naor, J.S., Schieber, B.: Message multicasting in het- erogeneous networks. SIAM Journal on Computing30(2), 347–358 (2000). https://doi.org/10.1137/S0097539798347906

    work page doi:10.1137/s0097539798347906 2000

  3. [3]

    In: Ganguly, S., Krishnamurti, R

    Bhabak, P., Harutyunyan, H.A.: Constant approximation for broadcasting in k- cycle graph. In: Ganguly, S., Krishnamurti, R. (eds.) Algorithms and Discrete Applied Mathematics. pp. 21–32. Springer International Publishing, Cham (2015)

    work page 2015

  4. [4]

    Bhabak, P., Harutyunyan, H.A., Concordia University (Montréal, Q., Concordia University (Montréal, Q.D.o.C.S., Engineering, S.: Approximation Algorithms for Broadcasting in Simple Graphs with Intersecting Cycles. Ph.D. thesis,[Concordia University],[Montréal, Québec](2015),http://spectrum.library.concordia. ca/979568/

    work page 2015

  5. [5]

    In: 2017 46th International Confer- ence on Parallel Processing Workshops (ICPPW)

    Bhabak, P., Harutyunyan, H.A., Kropf, P.: Efficient broadcasting al- gorithm in Harary-like networks. In: 2017 46th International Confer- ence on Parallel Processing Workshops (ICPPW). pp. 162–170 (2017). https://doi.org/10.1109/ICPPW.2017.34

    work page doi:10.1109/icppw.2017.34 2017

  6. [6]

    In: 2014 IEEE 17th International Conference on Computational Science and En- gineering

    Bhabak, P., Harutyunyan, H.A., Tanna, S.: Broadcasting in Harary-like graphs. In: 2014 IEEE 17th International Conference on Computational Science and En- gineering. pp. 1269–1276 (2014). https://doi.org/10.1109/CSE.2014.244

    work page doi:10.1109/cse.2014.244 2014

  7. [7]

    Journal of Combinatorial Optimization33(1), 292–316 (2017)

    Čevnik, M., Žerovnik, J.: Broadcasting on cactus graphs. Journal of Combinatorial Optimization33(1), 292–316 (2017). https://doi.org/10.1007/s10878-015-9957-8 Improved Approximation for Broadcasting in k-cycle Graphs 13

    work page doi:10.1007/s10878-015-9957-8 2017

  8. [8]

    Egami, Y., Gima, T., Hanaka, T., Kobayashi, Y., Lampis, M., Mitsou, V., Nemery, E., Otachi, Y., Vasilakis, M., Vaz, D.: Broadcasting under structural restrictions (2025),https://arxiv.org/abs/2504.13669, to appear in Proceedings of MFCS 2025

    work page arXiv 2025

  9. [9]

    In: Proceedings of the Thiry- Fourth Annual ACM Symposium on Theory of Computing

    Elkin, M., Kortsarz, G.: Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. In: Proceedings of the Thiry- Fourth Annual ACM Symposium on Theory of Computing. p. 438–447. STOC ’02, Association for Computing Machinery, New York, NY, USA (2002). https://doi.org/10.1145/509907.509972

    work page doi:10.1145/509907.509972 2002

  10. [10]

    Journal of Computer and System Sciences72(4), 648–659 (2006)

    Elkin, M., Kortsarz, G.: Sublogarithmic approximation for telephone mul- ticast. Journal of Computer and System Sciences72(4), 648–659 (2006). https://doi.org/https://doi.org/10.1016/j.jcss.2005.12.002

    work page doi:10.1016/j.jcss.2005.12.002 2006

  11. [11]

    In: Paulusma, D., Ries, B

    Fomin, F.V., Fraigniaud, P., Golovach, P.A.: Parameterized complexity of broad- casting in graphs. In: Paulusma, D., Ries, B. (eds.) Graph-Theoretic Concepts in Computer Science. pp. 334–347. Springer Nature Switzerland, Cham (2023)

    work page 2023

  12. [12]

    Theoretical Computer Science997, 114508 (2024)

    Fomin, F.V., Fraigniaud, P., Golovach, P.A.: Parameterized complexity of broadcasting in graphs. Theoretical Computer Science997, 114508 (2024). https://doi.org/https://doi.org/10.1016/j.tcs.2024.114508

    work page doi:10.1016/j.tcs.2024.114508 2024

  13. [13]

    Discrete Applied Mathematics53(1), 79–133 (1994)

    Fraigniaud, P., Lazard, E.: Methods and problems of communication in usual networks. Discrete Applied Mathematics53(1), 79–133 (1994). https://doi.org/https://doi.org/10.1016/0166-218X(94)90180-5

    work page doi:10.1016/0166-218x(94)90180-5 1994

  14. [14]

    Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA (1979)

    work page 1979

  15. [15]

    In: Pacheco, D.,Teixeira,A.S., Barbosa,H.,Menezes,R., Mangioni,G

    Gholami, S., Harutyunyan, H.A.: Broadcast graphs with nodes of limited memory. In: Pacheco, D.,Teixeira,A.S., Barbosa,H.,Menezes,R., Mangioni,G. (eds.)Com- plex Networks XIII. pp. 29–42. Springer International Publishing, Cham (2022)

    work page 2022

  16. [16]

    In: 2023 Fourteenth International Conference on Ubiquitous and Future Networks (ICUFN)

    Harutyunyan, H.A., Hovhannisyan, N., Maraachlian, E.: Broadcast- ing in chains of rings. In: 2023 Fourteenth International Conference on Ubiquitous and Future Networks (ICUFN). pp. 506–511 (2023). https://doi.org/10.1109/ICUFN57995.2023.10201234

    work page doi:10.1109/icufn57995.2023.10201234 2023

  17. [17]

    Harutyunyan, H.A., Liestman, A.L., , Peters, J.G., Richards, D.: Handbook of Graph Theory, chap. 12, pp. 1477–1494. Chapman Hall (2013)

    work page 2013

  18. [18]

    In: Lin, G

    Harutyunyan,H.A.,Maraachlian,E.:Linearalgorithmforbroadcastinginunicyclic graphs. In: Lin, G. (ed.) Computing and Combinatorics. pp. 372–382. Springer Berlin Heidelberg, Berlin, Heidelberg (2007)

    work page 2007

  19. [19]

    Journal of Combinatorial Optimization16(3), 307–322 (2008)

    Harutyunyan, H.A., Maraachlian, E.: On broadcasting in unicyclic graphs. Journal of Combinatorial Optimization16(3), 307–322 (2008). https://doi.org/10.1007/s10878-008-9160-2

    work page doi:10.1007/s10878-008-9160-2 2008

  20. [20]

    Networks18(4), 319–349 (1988)

    Hedetniemi, S.M., Hedetniemi, S.T., Liestman, A.L.: A survey of gossiping and broadcasting in communication networks. Networks18(4), 319–349 (1988). https://doi.org/https://doi.org/10.1002/net.3230180406

    work page doi:10.1002/net.3230180406 1988

  21. [21]

    Hromkovič, J., Klasing, R., Monien, B., Peine, R.: Dissemination of Information in Interconnection Networks (Broadcasting & Gossiping), pp. 125–212. Springer US, Boston, MA (1996). https://doi.org/10.1007/978-1-4757-2491-2_5,https://doi. org/10.1007/978-1-4757-2491-2_5

    work page doi:10.1007/978-1-4757-2491-2_5 1996

  22. [22]

    SIAM Journal on Discrete Mathematics8(3), 401–427 (1995)

    Kortsarz, G., Peleg, D.: Approximation algorithms for minimum-time broadcast. SIAM Journal on Discrete Mathematics8(3), 401–427 (1995). https://doi.org/10.1137/S0895480193245923

    work page doi:10.1137/s0895480193245923 1995

  23. [23]

    Middendorf, M.: Minimum broadcast time is np-complete for 3-regular pla- nar graphs and deadline 2. Inf. Process. Lett.46(6), 281–287 (Jul 1993). https://doi.org/10.1016/0020-0190(93)90066-I 14 J. Bringolf, A.-L. Ehresmann, and H. A. Harutyunyan

    work page doi:10.1016/0020-0190(93)90066-i 1993

  24. [24]

    IEEE Transactions on ComputersC- 30(5), 363–366 (1981)

    Proskurowski: Minimum broadcast trees. IEEE Transactions on ComputersC- 30(5), 363–366 (1981). https://doi.org/10.1109/TC.1981.1675796

    work page doi:10.1109/tc.1981.1675796 1981

  25. [25]

    In: Proceedings 35th Annual Symposium on Foundations of Computer Science

    Ravi, R.: Rapid rumor ramification: approximating the minimum broadcast time. In: Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 202–213 (1994). https://doi.org/10.1109/SFCS.1994.365693

    work page doi:10.1109/sfcs.1994.365693 1994

  26. [26]

    In: Jansen, K., Khuller, S

    Schindelhauer, C.: On the inapproximability of broadcasting time. In: Jansen, K., Khuller, S. (eds.) Approximation Algorithms for Combinatorial Optimization. pp. 226–237. Springer Berlin Heidelberg, Berlin, Heidelberg (2000)

    work page 2000

  27. [27]

    SIAM Journal on Computing10(4), 692–701 (1981)

    Slater, P.J., Cockayne, E.J., Hedetniemi, S.T.: Information dissemi- nation in trees. SIAM Journal on Computing10(4), 692–701 (1981). https://doi.org/10.1137/0210052

    work page doi:10.1137/0210052 1981

  28. [28]

    Theoretical Computer Science1045, 115282 (2025)

    Tale, P.: Telephone broadcast on graphs of treewidth two. Theoretical Computer Science1045, 115282 (2025). https://doi.org/https://doi.org/10.1016/j.tcs.2025.115282 Improved Approximation for Broadcasting in k-cycle Graphs 15 APPENDIX 7 Performance ofSimple-K-Cyclein Specific Cases In this section, we present two illustrative examples. The first demonstra...

    work page doi:10.1016/j.tcs.2025.115282 2025