Approximation algorithm for finding multipacking on Cactus

For a graph $ G = (V, E) $ with vertex set $ V $ and edge set $ E $, a function $ f : V \rightarrow \{0, 1, 2, . . . , diam(G)\} $ is called a \emph{broadcast} on $ G $. For each vertex $ u \in V $, if there exists a vertex $ v $ in $ G $ (possibly, $ u = v $) such that $ f (v) > 0 $ and $ d(u, v) \leq f (v) $, then $ f $ is called a \textit{dominating broadcast} on $ G $. The \textit{cost} of the dominating broadcast $f$ is the quantity $ \sum_{v\in V}f(v) $. The minimum cost of a dominating broadcast is the \textit{broadcast domination number} of $G$, denoted by $ \gamma_{b}(G) $. A \textit{multipacking} is a set $ S \subseteq V $ in a graph $ G = (V, E) $ such that for every vertex $ v \in V $ and for every integer $ r \geq 1 $, the ball of radius $ r $ around $ v $ contains at most $ r $ vertices of $ S $, that is, there are at most $ r $ vertices in $ S $ at a distance at most $ r $ from $ v $ in $ G $. The \textit{multipacking number} of $ G $ is the maximum cardinality of a multipacking of $ G $ and is denoted by $ mp(G) $. We show that, for any cactus graph $G$, $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$. We also show that $\gamma_b(G)-mp(G)$ can be arbitrarily large for cactus graphs by constructing an infinite family of cactus graphs such that the ratio $\gamma_b(G)/mp(G)=4/3$, with $mp(G)$ arbitrarily large. This result shows that, for cactus graphs, we cannot improve the bound $\gamma_b(G)\leq \frac{3}{2}mp(G)+\frac{11}{2}$ to a bound in the form $\gamma_b(G)\leq c_1\cdot mp(G)+c_2$, for any constant $c_1<4/3$ and $c_2$. Moreover, we provide an $O(n)$-time algorithm to construct a multipacking of $G$ of size at least $ \frac{2}{3}mp(G)-\frac{11}{3} $, where $n$ is the number of vertices of the graph $G$.