Improved Approximation for Broadcasting in k-cycle Graphs

Jeffrey Bringolf, Anne-Laure Ehresmann, Hovhannes A. Harutyunyan · 2025

Read Improved Approximation for Broadcasting in k-cycle Graphs by Jeffrey Bringolf, Anne-Laure Ehresmann, Hovhannes A. Harutyunyan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-26426.txt.

Introduction

Jeffrey Bringolf, Anne-Laure Ehresmann, and Hovhannes Harutyunyan sharpen a broadcasting algorithm for a special network shape in a 2025 paper. Broadcasting means one node starts a message and it must reach every node, passed hand to hand. Knowing the fastest broadcast time guides network design, but checking it is provably hard in general, and hard even for quite tame graph families.

Their focus is the tamest of all, k-cycle graphs, also called flower graphs, rings of cycles sharing one hub. They give a simple algorithm that runs in linear time. It lands within a factor of one and a half of the true best, minus a small bonus tied to the graph's shape. Taming even this small family took care, and the result closes part of a long hardness story.

Catalog record

CREATORJeffrey Bringolf, Anne-Laure Ehresmann, Hovhannes A. Harutyunyan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE32 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-26426

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Improved Approximation for Broadcasting in k-cycle Graphs Jeffrey Bringolf, Anne-Laure Ehresmann, Hovhannes A. Harutyunyan 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 v in an arbitrary network G G is known to be NP-hard. Additionally, recent findings show that the broadcast time problem is also NP-complete in general cactus graphs and some highly restricted subfamilies of cactus graphs. These graph families are structurally similar to k k -cycle graphs, in which the broadcast time problem is also believed to be NP-complete. In this paper, we present a simple ( 1.5 − ϵ ) (1.5-\epsilon) -approximation algorithm for determining the broadcast time of networks modeled using k k -cycle graphs, where ϵ > 0 \epsilon>0 depends on the structure of the graph. 1 Introduction Broadcasting is a crucial process for information dissemination in interconnected networks. As a result, a variety of network models have been studied at length [ 13 , 15 , 17 , 19 , 20 , 21 , 22 ] . These models have varying rules describing the means by which information can be disseminated. They may have different numbers of originators, numbers of receivers at each time unit, distances of each call, numbers of destinations, and other characteristics of the network such as knowledge of the neighbourhood available to each node. In this paper, we will focus on the classical model of broadcasting, sometimes referred to as telephone broadcasting . The network is modeled as an undirected connected graph G=(V,E) , where V(G) and E(G) denote the vertex set and the edge set of G , respectively. The classical model is described by the following assumptions. 1. The broadcasting process is split into discrete time units. 2. The only vertex that has the message before the first time unit is called originator . 3. In each time unit, an informed vertex ( sender ) can call at most one of its uninformed neighbors ( receiver ). 4. During each time unit, all calls are performed in parallel. 5. The process halts as soon as all the vertices in the graph are informed. Each call in the broadcasting process can be defined as \Gamma=(u,v) where u is the sender and v is the receiver. The broadcast scheme is represented by an ordered list containing the calls made by each vertex throughout the broadcast. This list can be represented by the sequence (\Gamma_{1},...,\Gamma_{t}) , where \Gamma_{i} is the set of calls made at time i and t is the time unit at which the network is fully informed. Definition 1 The broadcast time of a vertex v in a given graph G is the minimum number of time units required to broadcast in G if v is the originator and is denoted by b(v,G) . The broadcast time of a given graph G , is the maximum broadcast time from any originator in G , formally b(G)=max_{v\in V(G)}\{b(v,G)\} . The general broadcast time decision problem is formally defined as follows. Given a graph G=(V,E) with a specified set of vertices V_{0}\subseteq V and a positive integer k , is there a sequence V_{0},E_{1},V_{1},E_{2},V_{2},...,E_{k},V_{k} where V_{i}\subseteq V,E_{i}\subseteq E(1\leq i\leq k) , for every (u,v)\in E_{i},u\in V_{i-1},v\in V_{i},v\notin V_{i-1} and V_{k}=V . Here, k is the total broadcast time, V_{i} is the set of informed vertices at round i , and E_{i} is the set of edges used at round i . Clearly, when |V_{0}|=1 , this problem becomes our broadcast problem of determining b(v,G) for an arbitrary vertex v in an arbitrary graph G . The broadcast time decision problem is NP-complete in an arbitrary graph [ 14 , 27 ] . Furthermore, the problem was shown to be NP-complete in some restricted families of graphs, such as 3-regular planar graphs [ 23 ] . The study of the parameterized complexity of the broadcast time problem was initiated in [ 11 ] and has progressed in the following years [ 12 , 28 ] . Moreover, there are few classes of graphs for which an exact polynomial-time algorithm is known. Some examples of graph families for which exact linear time algorithms exist for the broadcast time problem are the following: trees [ 24 , 27 ] , unicyclic connected graphs [ 18 , 19 ] , necklace graphs (chain of rings) [ 16 ] , and Harary-like graphs [ 5 , 6 ] . The intractability of the broadcast time problem has led to significant work on approximation algorithms. Ravi devised a polynomial-time ( O(\frac{\log^{2}n)}{\log(\log n)}) )-approximation algorithm for the general broadcast time problem in [ 25 ] . This approximation ratio was improved to O(\log n) in [ 2 ] by Bar-Noy et al. Subsequently, Elkin and Kortsarz again improved the approximation ratio to the current best known approximation in general graphs of O(\frac{\log n}{\log(\log n)}) [ 9 , 10 ] . Additionally, the general broadcast time problem is known to be \frac{3}{2} -inapproximable from [ 26 ] . This was increased to a (3-\epsilon) -inapproximability result in [ 9 ] . Due to the significant advancements in the approximation of the general broadcast time problem, attention has been drawn to more constrained classes of graphs. Cactus graphs are a class of connected graphs in which any two simple cycles share at most one vertex. They have been a significant subject of interest in the field of graph algorithms as they are a simple class of graphs for which NP-hard problems have polynomial solutions. An exact algorithm to solve the broadcast time problem in cactus graphs was given in [ 7 ] . The complexity of the algorithm on a cactus graph G=(V,E) is O(kk!m+n) where m=|E| , n=|V| , and k is the maximum number of cycles that share a vertex. In a k -restricted cactus graph , k is held constant, and the algorithm is polynomial. Nonetheless, until recently, the tractability of the problem on general cactus graphs remained an open question. Moreover, the problem remains open even for very simple graph families, such as those formed by merging k cycles at a single vertex. These graphs, called k-cycle graphs or flower graphs , are the focus of this paper. Very recent results come quite close to determining the complexity of the broadcast time problem in k -cycle graphs. In particular, several new findings have been published regarding the broadcast time problem in cactus graphs, which are closely related to k -cycle graphs. The first finding is the proof that the broadcast time problem is NP-complete in so-called "snowflake graphs" by Aminian et al. [ 1 ] . Snowflake graphs are a subclass of cactus graphs that have a pathwidth of at most 2. Thus, by proving the intractability of the problem in this particular graph family, they also showed that the complexity of the broadcast time problem is NP-complete in both general cactus graphs and general graphs with pathwidth at most 2. See Figure 1 for an example of a snowflake graph.

Read the complete text