Broadcast Domination Number is at Most Twice the Multipacking Number

Abstract

For a graph $G=(V,E)$ with a vertex set $V$ and an edge set $E$, a function $f:V\rightarrow\{0,1,2,...,diam(G)\}$ is called a 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 dominating broadcast on $G$. The cost of the dominating broadcast $f$ is the quantity $\sum_{v\in V}f(v)$. The minimum cost of a dominating broadcast is the broadcast domination number of $G$, denoted by $\gamma_{b}(G)$.

A multipacking is a set $M\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 $M$, that is, there are at most $r$ vertices in $M$ at a distance at most $r$ from $v$ in $G$. The multipacking number of $G$ is the maximum cardinality of a multipacking of $G$ and is denoted by $\MP(G)$.

It is known that $\MP(G)\leq\gamma_{b}(G)$. In 2014, Hartnell and Mynhardt proved that $\gamma_{b}(G)\leq 3\MP(G)-2$ whenever $\MP(G)\geq 2$. In 2019, Beaudou, Brewster, and Foucaud improved this bound to $\gamma_{b}(G)\leq 2\MP(G)+3$ and conjectured that $\gamma_{b}(G)\leq 2\MP(G)$. We solve their conjecture by proving that $\gamma_{b}(G)\leq 2\MP(G)$ for every graph $G$. Our proof is constructive and yields a polynomial-time $2$-approximation algorithm for Maximum Multipacking problem which improves the earlier approximation factor $2+o(1)$.

2012 ACM Subject Classification: Theory of computation $\rightarrow$ Graph algorithms analysis; Mathematics of computing $\rightarrow$ Graph theory.

1 Introduction

Covering and packing are fundamental problems in graph theory and algorithms [4]. We study two dual covering and packing problems called broadcast domination and multipacking. The broadcast domination problem is motivated by telecommunication networks. Imagine a network with radio towers that can transmit information within a certain radius $r$ for a cost of $r$. The goal is to cover the entire network while minimizing the total cost. The multipacking problem is its natural packing counterpart and generalizes various other standard packing problems. Unlike many standard packing and covering problems, these two problems involve arbitrary distances in graphs, which makes them challenging. The goal of this paper is to study the relation between these two parameters in general graphs.

For a graph $G=(V,E)$, $d_{G}(u,v)$ is the length of a shortest path joining two vertices $u$ and $v$ in $G$, and we simply write $d(u,v)$ when there is no confusion. Let $N_{r}[v]:=\{u\in V:d(v,u)\leq r\}$, i.e. a ball of radius $r$ around $v$. The eccentricity $e(w)$ of a vertex $w$ is $\min\{r:N_{r}[w]=V\}$. The radius of the graph $G$ is $\min\{e(w):w\in V\}$, denoted by $\rad(G)$. The diameter of the graph $G$ is $\max\{d(u,v):u,v\in V\}$, denoted by $\mathrm{diam}(G)$. A shortest path of length $\diam(G)$ is called a diametral path of $G$.

The covering problem we study is broadcast domination. For a graph $G=(V,E)$ with vertex set $V$, edge set $E$ and diameter $\diam(G)$, a function $f:V\rightarrow\{0,1,2,...,\diam(G)\}$ is called a broadcast on $G$. Suppose $G$ is a graph with a broadcast $f$. 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 dominating broadcast on $G$. Its cost is $\sigma(f)=\sum_{v\in V}f(v)$. The minimum cost of a dominating broadcast in $G$ (taken over all dominating broadcasts) is the broadcast domination number of G, denoted by $\gamma_{b}(G)$. So, $\gamma_{b}(G)=\min_{f\in D(G)}\sigma(f)$, where $D(G)$ is the set of all dominating broadcasts on $G$. We follow the convention $\gamma_{b}(K_{1})=1$ for the one-vertex graph.

An optimal broadcast or minimum dominating broadcast on a graph $G$ is a dominating broadcast with a cost equal to $\gamma_{b}(G)$. Define a ball of radius $r$ around $v$ by $N_{r}[v]=\{u\in V(G):d(v,u)\leq r\}$. Suppose $V(G)=\{v_{1},v_{2},v_{3},\dots,v_{n}\}$. Let $c$ and $x$ be the vectors indexed by $(i,k)$ where $v_{i}\in V(G)$ and $1\leq k\leq\diam(G)$, with the entries $c_{i,k}=k$ and $x_{i,k}=1$ when $f(v_{i})=k$ and $x_{i,k}=0$ when $f(v_{i})\neq k$. Let $A=[a_{j,(i,k)}]$ be a matrix with the entries

$a_{j,(i,k)}=\begin{cases}1&\text{if }v_{j}\in N_{k}[v_{i}]\\ 0&\text{otherwise. }\end{cases}$

Hence, the broadcast domination number can be expressed as an integer linear program:

$\gamma_{b}(G)=\min\{c\cdot x:Ax\geq\mathbf{1},x_{i,k}\in\{0,1\}\}.$

The maximum multipacking problem is the dual integer program of the above problem. In 2013, Brewster, Mynhardt, and Teshima [3] formally defined multipacking. A multipacking is a set $M\subseteq V$ in a graph $G=(V,E)$ such that $|N_{r}[v]\cap M|\leq r$ for each vertex $v\in V(G)$ and for every integer $r\geq 1$. The multipacking number of $G$ is the maximum cardinality of a multipacking of $G$ and it is denoted by $\MP(G)$. A maximum multipacking is a multipacking $M$ of a graph $G$ such that $|M|=\MP(G)$. If $M$ is a multipacking, we define a vector $y$ with the entries $y_{j}=1$ when $v_{j}\in M$ and $y_{j}=0$ when $v_{j}\notin M$. So,

$\MP(G)=\max\{y\cdot\mathbf{1}:yA\leq c,y_{j}\in\{0,1\}\}.$

Brief Survey: Broadcast domination was introduced by Erwin, while multipacking was introduced by Teshima as its natural packing counterpart; see [10, 3, 1]. Hartnell and Mynhardt proved that $\gamma_{b}(G)\leq 3\MP(G)-2$ whenever $\MP(G)\geq 2$ [11]. Beaudou, Brewster, and Foucaud later improved this to $\gamma_{b}(G)\leq 2\MP(G)+3$ and conjectured that $\gamma_{b}(G)\leq 2\MP(G)$ for every graph [1]. The conjectured coefficient is the best possible, because a recent work gives a family of hypercubes for which $\gamma_{b}(G)/\MP(G)$ tends to $2$ for arbitrarily large $\MP(G)$ [13]. From an algorithmic viewpoint, Minimum Dominating Broadcast can be solved in polynomial time [12]. Whereas, Multipacking problem is NP-complete [7] and there is a $(2+o(1))$-approximation algorithm for general graphs [1]. Polynomial-time algorithms are known for trees and, more generally, for strongly chordal graphs [2]. Approximation algorithms with ratio $(\tfrac{3}{2}+o(1))$ have been obtained for chordal graphs [5, 6] and cactus graphs [8].

Our Contribution: First, we strengthen the previously known relation $\MP(G)\geq(\rad(G)-3)/2$ between the multipacking number and the radius of a connected graph [1].

Theorem 1.1

Let $G$ be a connected graph with radius $r$. Then $\MP(G)\geq\left\lfloor r/2\right\rfloor$.

Next, we prove the conjecture of Beaudou, Brewster, and Foucaud [1] and improve their bound $\gamma_{b}(G)\leq 2\MP(G)+3$. We use a two-path structure similar to the one used in their work, but modify the selection of the multipacking vertices. For the only case not resolved by this modified construction, we use a ball-cover argument to find an additional vertex that can be added to the multipacking.

Theorem 1.2

For every graph $G$, $\gamma_{b}(G)\leq 2\MP(G)$.

Finally, the multipacking construction used to prove the conjecture is algorithmic. It yields a polynomial-time $2$-approximation algorithm for Maximum Multipacking. This improves the earlier approximation factor $2+o(1)$ [1].

Theorem 1.3

There is a polynomial-time $2$-approximation algorithm for Maximum Multipacking.

Organisation: In Section 2, we present the definitions and basic results used throughout the paper. In Section 3, we establish the relation between the multipacking number and the radius. In Section 4, we prove the main bound relating broadcast domination and multipacking. In Section 5, we present the resulting approximation algorithm for Maximum Multipacking. Finally, we conclude in Section 6.

2 Preliminaries

All graphs are finite, simple, and undirected. Unless stated otherwise, they are connected and have at least two vertices. A path $P=(v_{0},v_{1},\ldots,v_{\ell})$ is called isometric if $d(v_{i},v_{j})=|i-j|$ for all $0\leq i,j\leq\ell$. Equivalently, an isometric path is a shortest path between its end vertices.

It is known that for every connected graph $G$, $\MP(G)\leq\gamma_{b}(G)\leq\rad(G)$ [3, 9, 10]. The following useful criterion is due to Beaudou, Brewster, and Foucaud [1].

Lemma 1 ([1])

Let $M\subseteq V(G)$. If, for every subset $U\subseteq M$ with $|U|\geq 2$, there exists two vertices $x,y\in U$ satisfies $d(x,y)\geq 2|U|-1$, then $M$ is a multipacking of $G$.

This can be proved by contradiction. If $M$ is not a multipacking, some ball $N_{r}[z]$ contains a set $U\subseteq M$ of at least $r+1$ vertices. Every two vertices in $U$ are at distance at most $2r\leq 2|U|-2$, so $U$ fails to satisfy the stated property.

3 Relation Between Broadcast Domination Number and Radius (Proof of Theorem 1.1)

Figure 1: The horizontal path is an isometric path $P=(x_{0},\ldots,x_{L})$, and $Q=(z_{0},\ldots,z_{R})$ is an isometric path with initial vertex $z_{0}=x_{3k}$. The black disk vertices represent multipacking on these paths.

Let $P=(x_{0},x_{1},\ldots,x_{L})$ and $Q=(z_{0},z_{1},\ldots,z_{R})$ be isometric paths in a graph $G$ such that $z_{0}=x_{h}$; see Figure 1. Then, for all indices $i$ and $j$,

$$d(x_{i},z_{j})\geq j-|i-h|.$$ (1)

This is true because, by the triangle inequality, we have $d(x_{h},z_{j})\leq d(x_{h},x_{i})+d(x_{i},z_{j})$, where $d(x_{h},z_{j})=d(z_{0},z_{j})=j$ and $d(x_{h},x_{i})=|i-h|$.

Lemma 2

Let $R\geq 1$, $k=\left\lfloor R/6\right\rfloor$, $p=\left\lfloor R/3\right\rfloor$, and $\ell=\left\lfloor(R-1)/6\right\rfloor$. Let $G$ be a graph that contains isometric paths $P=(x_{0},\ldots,x_{L})$ and $Q=(z_{0},\ldots,z_{R})$, where $L\geq R$ and $z_{0}=x_{3k}$. Then

$$M_{R}=\{x_{3i}:0\leq i\leq p\}\cup\{z_{R-3j}:0\leq j<\ell\}$$ (2)

is a multipacking in $G$. Moreover,

$$|M_{R}|=\begin{cases}\left\lceil R/2\right\rceil,&R\not\equiv 5\pmod{6},\\ (R-1)/2,&R\equiv 5\pmod{6}.\end{cases}$$

Proof

Let $R=6k+\rho$, where $\rho\in\{0,1,2,3,4,5\}$, and $h=3k$. Let $A=\{x_{3i}:0\leq i\leq p\}$ and $B=\{z_{R-3j}:0\leq j<\ell\}$, therefore $M_{R}=A\cup B$. The largest distance along $P$ from a vertex of $A$ to $x_{h}$ is

$$D_{\rho}=\max\{|i-h|:x_{i}\in A\}=\begin{cases}3k,&\rho\in\{0,1,2\},\\ 3k+3,&\rho\in\{3,4,5\}.\end{cases}$$

When $B\neq\emptyset$, its smallest index is

$$b_{\rho}=\min\{j:z_{j}\in B\}=\begin{cases}3k+6,&\rho=0,\\ 3k+\rho+3,&\rho\in\{1,2,3,4,5\}.\end{cases}$$

Therefore, $b_{\rho}>D_{\rho}$ for each $\rho\in\{0,1,2,3,4,5\}$. Hence $A\cap B=\emptyset$.

Now $p=2k$ for $\rho\in\{0,1,2\}$ and $p=2k+1$ for $\rho\in\{3,4,5\}$, while $\ell=k-1$ for $\rho=0$ and $\ell=k$ otherwise. Therefore,

$$|A|=p+1=\begin{cases}2k+1,&\rho\in\{0,1,2\},\\ 2k+2,&\rho\in\{3,4,5\}.\end{cases}$$

and

$$|B|=\ell=\begin{cases}k-1,&\rho=0\\ k,&\rho\in\{1,2,3,4,5\}.\end{cases}$$

Consequently,

$$|M_{R}|=|A|+|B|=\begin{cases}3k,&\rho=0,\\ 3k+1,&\rho\in\{1,2\},\\ 3k+2,&\rho\in\{3,4,5\},\end{cases}$$

which implies

$$|M_{R}|=\begin{cases}\left\lceil R/2\right\rceil,&R\not\equiv 5\pmod{6},\\ (R-1)/2,&R\equiv 5\pmod{6}.\end{cases}$$

We prove $M_{R}$ is a multipacking of $G$ using Lemma 1. Let $U\subseteq M_{R}$ with $|U|=t\geq 2$. If $U\subseteq A$ or $U\subseteq B$, then the vertices of $U$ occur at indices differing by multiples of three on an isometric path. Consequently, the vertices of $U$ having minimum and maximum indices are at distance at least $3(t-1)\geq 2t-1$.

Assume henceforth that $\alpha=|U\cap A|\geq 1$, $\beta=|U\cap B|\geq 1$, and $t=\alpha+\beta$. Let $s=\min\{|i-h|:x_{i}\in U\cap A\}$. Choose $i^{*}$ such that $x_{i^{*}}\in U\cap A$ and $|i^{*}-h|=s$, and let $j^{*}=\max\{j:z_{j}\in U\cap B\}$. Since the indices of the vertices of $B$ form an arithmetic progression with common difference three and $|U\cap B|=\beta$, we have $j^{*}\geq b_{\rho}+3(\beta-1)$. By (1),

$$d(x_{i^{*}},z_{j^{*}})\geq b_{\rho}+3(\beta-1)-s.$$ (3)

Suppose, for contradiction, we assume that every two vertices of $U$ are at distance at most $2t-2$. Comparing this upper bound with (3) gives

$$s\geq b_{\rho}+\beta-2\alpha-1.$$ (4)

Let $I_{A}=\{i:x_{i}\in U\cap A\}$. Assume first that either $I_{A}\subseteq\{0,\ldots,h\}$ or $I_{A}\subseteq\{h,\ldots,L\}$. Within either of the two index intervals, consecutive indices corresponding to vertices of $A$ differ by three. Hence, among any $\alpha$ such indices, the minimum value of $|i-h|$ is at most $D_{\rho}-3(\alpha-1)$. Combining this with (4) yields $\alpha+\beta\leq D_{\rho}+4-b_{\rho}$. For $\rho=0,1,\ldots,5$, the quantity on the right is, respectively, $-2,0,-1,1,0,-1$. This contradicts $\alpha+\beta\geq 2$.

It follows that there exist indices $i_{-},i_{+}\in I_{A}$ satisfying $i_{-}<h<i_{+}$. Let $i_{\min}=\min I_{A}$ and $i_{\max}=\max I_{A}$. We claim that

$$i_{\max}-i_{\min}\geq 2s+3(\alpha-2).$$ (5)

Let $\alpha_{-}$ and $\alpha_{+}$ denote the numbers of indices in $I_{A}$ smaller and larger than $h$, respectively. Note that both $\alpha_{-}$ and $\alpha_{+}$ are positive. If $h\notin I_{A}$, then $\alpha_{-}+\alpha_{+}=\alpha$. Therefore $i_{\max}-i_{\min}\geq\bigl(s+3(\alpha_{-}-1)\bigr)+\bigl(s+3(\alpha_{+}-1)\bigr)=2s+3(\alpha-2).$ If $h\in I_{A}$, then $s=0$ and $\alpha_{-}+\alpha_{+}=\alpha-1$. Since both $\alpha_{-}$ and $\alpha_{+}$ are positive, $i_{\max}-i_{\min}\geq 3\alpha_{-}+3\alpha_{+}=3(\alpha-1)\geq 2s+3(\alpha-2).$ This proves (5).

Since $P$ is isometric, we have $d(x_{i_{\min}},x_{i_{\max}})=i_{\max}-i_{\min}$. Recall, we assumed that every two vertices of $U$ are at distance at most $2t-2$. This fact and (4) yield $2(\alpha+\beta)-2\geq 2s+3(\alpha-2)\geq 2(b_{\rho}+\beta-2\alpha-1)+3\alpha-6,$ which simplifies to

$$3\alpha\geq 2b_{\rho}-6.$$ (6)

For $\rho\in\{0,2,4,5\}$, (6) gives $\alpha\geq 2k+2,\alpha\geq 2k+2,\alpha\geq 2k+3$, and $\alpha\geq 2k+4$ respectively. Each bound exceeds $|A|$, so this is a contradiction.

Suppose $\rho=1$. Then (6) implies $\alpha=|A|=2k+1$, so $A\subseteq U$. In particular, $x_{0},x_{6k}\in U$, and hence $6k=d(x_{0},x_{6k})\leq 2|U|-2=2(2k+1+\beta)-2.$ Thus $\beta\geq k$. Since $|B|=k$, we have $U=M_{R}$. Moreover, $z_{0}=x_{3k}\in A$ and $z_{R}\in B$, so $d(z_{0},z_{R})=R=6k+1=2|M_{R}|-1=2|U|-1$, which contradicts the assumption on $U$.

Suppose $\rho=3$. Then (6) implies $\alpha=|A|=2k+2$. Hence $A\subseteq U$, and the two vertices $x_{0},x_{6k+3}\in U$ satisfy $d(x_{0},x_{6k+3})=6k+3$. Under the contradiction assumption, $6k+3\leq 2|U|-2=2(2k+2+\beta)-2$, which implies $\beta\geq k+1>|B|$, a contradiction.

Every case is contradictory. Hence, by Lemma 1, $M_{R}$ is a multipacking of $G$.

$\square$

Lemma 3

Let $G$ be a connected graph of radius $r\geq 1$. Then

$$\MP(G)\geq\begin{cases}\left\lceil r/2\right\rceil,&r\not\equiv 5\pmod{6},\\ (r-1)/2,&r\equiv 5\pmod{6}.\end{cases}$$

Proof

As $\diam(G)\geq r$, choose an isometric path $P=(x_{0},\ldots,x_{r})$ of length $r$. Let $k=\left\lfloor r/6\right\rfloor$ and $c=x_{3k}$. Every vertex has eccentricity at least $r$, so there is a vertex $w$ with $d(c,w)\geq r$. Take a subpath $Q$ of length $r$ of a shortest path from $c$ to $w$. Let $Q=(z_{0},\ldots,z_{r})$ with $z_{0}=c$. $Q$ is also an isometric path. Apply Lemma 2 with $R=L=r$. $\square$

Therefore, if $G$ is a connected graph with radius $r$, then $\MP(G)\geq\left\lfloor r/2\right\rfloor$, by Lemma 3. This proves Theorem 1.1.

Corollary 1

For every connected graph $G$, $\gamma_{b}(G)\leq 2\MP(G)+1$. Moreover, the stronger inequality $\gamma_{b}(G)\leq 2\MP(G)$ holds unless $\rad(G)\equiv 5\pmod{6}$ and $\gamma_{b}(G)=\rad(G)$.

Proof

The result is immediate for $G=K_{1}$, so assume that $G$ has at least two vertices. Let $r=\rad(G)$. Since $\left\lceil r/2\right\rceil\geq(r-1)/2$, we have $\MP(G)\geq\frac{r-1}{2}\geq\frac{\gamma_{b}(G)-1}{2}$ by Lemma 3. If $r\not\equiv 5\pmod{6}$, then $\MP(G)\geq\left\lceil r/2\right\rceil\geq r/2\geq\gamma_{b}(G)/2$ by Lemma 3. If $\gamma_{b}(G)\leq r-1$, then by Theorem 1.1, $\MP(G)\geq\left\lfloor r/2\right\rfloor\geq\frac{r-1}{2}\geq\frac{\gamma_{b}(G)}{2}$.

$\square$

4 Relation between Broadcast Domination and Multipacking Number (Proof of Theorem 1.2)

We now consider the only case left by Corollary 1, namely, $\rad(G)\equiv 5\pmod{6}$ and $\gamma_{b}(G)=\rad(G)$. For the construction below, let $R=\rad(G)=6k+5$, where $k\geq 1$. Choose an isometric path $P=(x_{0},x_{1},\ldots,x_{R})$, put $c=x_{3k}$, and choose a vertex $w$ satisfying $d(c,w)\geq R$. Let $Q=(z_{0},z_{1},\ldots,z_{R})$ with $z_{0}=c$ be a subpath of length $R$ of a shortest path from $c$ to $w$. Then $Q$ is isometric. Since $R=6k+5$, we have $\left\lfloor R/3\right\rfloor=2k+1$ and $\left\lfloor(R-1)/6\right\rfloor=k$. Let $X_{i}=x_{3i}$ for $0\leq i\leq 2k+1$ and $Z_{j}=z_{R-3j}$ for $0\leq j\leq k-1$. Then the set $M_{R}$ from Lemma 2 can be written as

$$M_{R}=\{X_{i}:0\leq i\leq 2k+1\}\cup\{Z_{j}:0\leq j\leq k-1\}.$$ (7)

By Lemma 2, $M_{R}$ is a multipacking of size $3k+2$. For all indices $i,j$,

$$d(X_{i},Z_{j})\geq R-3j-3|i-k|.$$ (8)

This is true because, by the triangle inequality, we have $d(X_{k},Z_{j})\leq d(X_{k},X_{i})+d(X_{i},Z_{j})$.

Figure 2: The horizontal path is an isometric path $P=(x_{0},\ldots,x_{R})$, and $Q=(z_{0},\ldots,z_{R})$ is an isometric path with initial vertex $z_{0}=x_{3k}$. The black disk vertices on $P$ and $Q$ represent vertices of multipacking $M_{R}$. The vertex $b$ is added to multipacking $M_{R}$ later.

For proving the remaining case of Theorem 1.2, we need the following lemma.

Lemma 4

Every $T\subseteq M_{R}$ with $|T|=t\geq 4$ contains two vertices whose distance is at least $2t+1$.

Proof

Let $A=\{X_{i}:0\leq i\leq 2k+1\}$ and $B=\{Z_{j}:0\leq j\leq k-1\}$. So, $M_{R}=A\cup B$. Let $T\subseteq M_{R}$ with $|T|=t$.

If $T\subseteq A$ or $T\subseteq B$, then the vertices of $T$ corresponding to the minimum and maximum indices are at distance at least $3(t-1)$. Since $t\geq 4$, we have $3(t-1)\geq 2t+1$.

Assume that $T$ intersects both $A$ and $B$. Let $\alpha=|T\cap A|$, $\beta=|T\cap B|$, and $t=\alpha+\beta$. Define $I=\{i:X_{i}\in T\}$ and $J=\{j:Z_{j}\in T\}$, and let $s=\min_{i\in I}|i-k|$.

Let $j_{0}=\min J$. Since $J$ contains $\beta$ distinct indices from $\{0,1,\ldots,k-1\}$, we have $j_{0}\leq k-\beta$. Choose $i_{0}\in I$ such that $|i_{0}-k|=s$. By (8),

$$d(X_{i_{0}},Z_{j_{0}})\geq R-3j_{0}-3|i_{0}-k|\geq 3k+5+3\beta-3s.$$ (9)

Suppose, for contradiction, we assume that every pair of vertices in $T$ is at distance at most $2t$. Inequality (9) gives

$$3s\geq 3k+\beta+5-2\alpha.$$ (10)

Assume first that either $I\subseteq\{0,\ldots,k\}$ or $I\subseteq\{k,\ldots,2k+1\}$. In the first case, $s\leq k+1-\alpha$, while in the second case, $s\leq k+2-\alpha$. Thus, in either case, $s\leq k+2-\alpha$. Combining this with (10) gives $3k+\beta+5-2\alpha\leq 3k+6-3\alpha$, and hence $\alpha+\beta\leq 1$. This contradicts $\alpha,\beta\geq 1$.

It follows that there exist $i_{-},i_{+}\in I$ such that $i_{-}<k<i_{+}$. Let $i_{\min}=\min I$ and $i_{\max}=\max I$. We claim that $i_{\max}-i_{\min}\geq 2s+\alpha-2$.

Let $\alpha_{-}$ and $\alpha_{+}$ be the numbers of indices in $I$ smaller and larger than $k$, respectively. If $k\notin I$, then $\alpha_{-}+\alpha_{+}=\alpha$, and hence $i_{\max}-i_{\min}\geq(s+\alpha_{-}-1)+(s+\alpha_{+}-1)=2s+\alpha-2$. If $k\in I$, then $s=0$ and $\alpha_{-}+\alpha_{+}=\alpha-1$. Therefore, $i_{\max}-i_{\min}\geq\alpha_{-}+\alpha_{+}=\alpha-1\geq 2s+\alpha-2$.

Since $P$ is isometric, $d(X_{i_{\min}},X_{i_{\max}})=3(i_{\max}-i_{\min})$. Under the contradiction assumption, we obtain $3(2s+\alpha-2)\leq 2t$, and consequently $6s+\alpha\leq 2\beta+6$. Combining this with (10) gives $3\alpha\geq 6k+4$. Since $\alpha\leq 2k+2$, we must have $\alpha=2k+2$. Hence $I=\{0,1,\ldots,2k+1\}$ and $s=0$.

Substituting $\alpha=2k+2$ and $s=0$ into (10) gives $\beta\leq k-1$. On the other hand, $X_{0},X_{2k+1}\in T$, and therefore $d(X_{0},X_{2k+1})=6k+3$. The contradiction assumption gives $6k+3\leq 2t=2(2k+2+\beta)$, which implies $\beta\geq k$. This contradicts $\beta\leq k-1$.

Therefore, $T$ contains two vertices whose distance is at least $2t+1$. $\square$

Lemma 5

Let $G$ be a graph with $\rad(G)\equiv 5\pmod{6}$ and $\gamma_{b}(G)=\rad(G)$. Then $\gamma_{b}(G)\leq 2\MP(G)$.

Proof

Take $R=\rad(G)=\gamma_{b}(G)=6k+5$.

First suppose $k=0$. Choose vertices $u,v$ at distance $5$, i.e. $d(u,v)=5$. The two radius-$2$ balls centered at $u$ and $v$ have total cost $4$. If they covered $G$, they would define a dominating broadcast of cost $4$, contradicting $\gamma_{b}(G)=5$. Therefore, they do not cover $G$. Choose $w$ outside their union. Then $d(u,v)=5$ and $d(w,u),d(w,v)\geq 3$. The set $\{u,v,w\}$ is a multipacking, since a radius-$1$ ball contains at most one of its vertices, a radius-$2$ ball cannot contain both $u$ and $v$, and larger radii are trivial. Thus $\MP(G)\geq 3$ and $\gamma_{b}(G)=5\leq 6$.

Assume now $k\geq 1$. Choose the paths $P,Q$ and the set $M_{R}$ as we described at the starting of this section.

Consider the two balls

$$N_{3k+5}[x_{3k+3}]\quad\text{and}\quad N_{3k-1}[z_{R}].$$ (11)

Their radii sum to $6k+4=R-1$. If they covered $G$, they would define a dominating broadcast of cost $R-1$, contradicting $\gamma_{b}(G)=R$. Therefore, they do not cover $G$. Choose $b\in V(G)$ outside their union. Then

$$d(b,x_{3k+3})\geq 3k+6\quad\text{and}\quad d(b,z_{R})\geq 3k.$$ (12)

Every $X_{i}$ is within distance $3k+3$ of $x_{3k+3}$, and every $Z_{j}$ is within distance $3k-3$ of $z_{R}$. Hence $b\notin M_{R}$, and $M_{R}\cup\{b\}$ has size $3k+3$. Let $M=M_{R}\cup\{b\}$; see Figure 2.

We prove that $M$ is a multipacking of $G$. Let $N_{r}[v]$ be any ball with integer radius $r\geq 1$. If $b\notin N_{r}[v]$, then $|N_{r}[v]\cap M|\leq r$ because $M_{R}$ is a multipacking by Lemma 2. Suppose that $b\in N_{r}[v]$, and let $T=N_{r}[v]\cap M_{R}$ and $t=|T|$. We have $t\leq r$, since $M_{R}$ is a multipacking. There is nothing to prove when $t\leq r-1$, so assume $t=r$. Therefore, from now, we consider the case where $b\in N_{r}[v]$ and $t=r$.

If $r\geq 4$, Lemma 4 gives two vertices of $T$ at distance at least $2r+1$, impossible inside a radius-$r$ ball.

Suppose that $r\in\{1,2,3\}$. From triangle inequality, we have $d(b,X_{i})\geq d(b,X_{k+1})-d(X_{i},X_{k+1})$ and $d(b,Z_{j})\geq d(b,Z_{0})-d(Z_{j},Z_{0})$. Therefore, from (12),

$$d(b,X_{i}) \geq 3k+6-3|i-(k+1)|, 0\leq i\leq 2k+1,$$ (13)

$$d(b,Z_{j}) \geq 3k-3j, 0\leq j\leq k-1.$$ (14)

Both lower bounds are at least $3$. Thus a radius-$1$ ball containing $b$ contains no vertex of $M_{R}$.

For $r=2$, every vertex of $T$ is within distance $4$ of $b$. Inequalities (13) and (14) show that the only possibilities are $X_{0}$ and $Z_{k-1}$. But $d(X_{0},Z_{k-1})\geq 8$ by (8), whereas two vertices in a radius-$2$ ball are at distance at most $4$.

For $r=3$, every vertex of $T$ is within distance $6$ of $b$. Inequalities (13) and (14) show that the only possibilities are $X_{0},X_{1},X_{2k+1},Z_{k-2},Z_{k-1}$. Suppose $k=1$. We can exclude $Z_{k-2}$. Every three of the four remaining vertices contain one of the pairs $\{X_{0},X_{3}\}$, $\{X_{0},Z_{0}\}$, or $\{X_{1},Z_{0}\}$, whose distances are at least $9$, $8$, and $11$, respectively. The first bound follows because $P$ is isometric and $d(X_{0},X_{3})=9$, while the remaining bounds follow from (8). If $k\geq 2$, every three vertices from $X_{0},X_{1},X_{2k+1},Z_{k-2},Z_{k-1}$ contain one of the pairs $\{X_{0},X_{2k+1}\}$, $\{X_{0},Z_{k-1}\}$, $\{X_{0},Z_{k-2}\}$, $\{X_{1},Z_{k-1}\}$, or $\{X_{2k+1},Z_{k-2}\}$. The distances of these pairs are at least $15$, $8$, $11$, $11$, and $8$, respectively. The first bound follows because $P$ is isometric and $d(X_{0},X_{2k+1})=6k+3\geq 15$, while the remaining bounds follow from (8). Thus the three vertices of $T$ contain a pair at distance at least $7$, which is impossible in a radius-$3$ ball.

Consequently, $M$ is a multipacking, so $\MP(G)\geq 3k+3$. Finally, $\gamma_{b}(G)=6k+5<6k+6=2(3k+3)\leq 2\MP(G).$ $\square$

Thus Corollary 1 and Lemma 5 yield Theorem 1.2.

5 Approximation Algorithm (Proof of Theorem 1.3)

The proof of Theorem 1.1 and 1.2 can be turned into an approximation algorithm without computing $\gamma_{b}(G)$.

Lemma 6

There is a polynomial-time algorithm that, given a connected graph $G$, constructs a multipacking $M$ of $G$ satisfying $|M|\geq\MP(G)/2$.

Proof

If $G=K_{1}$, return its unique vertex. Otherwise, compute $r=\rad(G)$ and construct the isometric paths $P$ and $Q$ as in the proof of Lemma 3.

If $r\not\equiv 5\pmod{6}$, return the multipacking $M_{r}$ from Lemma 2. Suppose that $r=6k+5$. If $k=0$, choose vertices $u,v$ with $d(u,v)=5$ and test whether $N_{2}[u]\cup N_{2}[v]$ covers $G$. Return $\{u,v\}$ if it does; otherwise, choose a vertex $b$ outside these balls and return $\{u,v,b\}$.

If $k\geq 1$, construct the multipacking $M_{r}$ from Lemma 2 and test whether the two balls in (11) cover $G$. Return $M_{r}$ if they do; otherwise, choose a vertex $b$ outside their union and return $M_{r}\cup\{b\}$. Lemma 2 and the proof of Lemma 5 show that every set returned by the algorithm is a multipacking.

In each case where the balls cover $G$, they define a dominating broadcast of cost $2|M|$, and hence $\MP(G)\leq\gamma_{b}(G)\leq 2|M|$. In every other case, $|M|\geq\left\lceil r/2\right\rceil$, while $\MP(G)\leq\gamma_{b}(G)\leq r$. Therefore $|M|\geq\MP(G)/2$.

The radius, the required paths, the balls, and an uncovered vertex can all be computed in polynomial time using breadth-first search. $\square$

For disconnected graphs, both parameters are additive over components, so the main inequality extends componentwise.

Hence, there is a polynomial time $2$-approximation algorithm for Maximum Multipacking.

6 Conclusion

The factor $2$ in Theorem 1.2 cannot be reduced. Equality already occurs for $C_{4}$ and $C_{5}$, where $\gamma_{b}(G)=2$ and $\MP(G)=1$. For more examples, see [14]. More significantly, hypercubes form an infinite family of connected graphs for which the ratio $\gamma_{b}(G)/\MP(G)$ tends to $2$ for arbitrarily large $\MP(G)$ [13].

We provide a polynomial-time $2$-approximation algorithm for Maximum Multipacking. The implementation described in this paper first computes $r=\rad(G)$. This can be done by running breadth-first search (BFS) from every vertex, in $O(n(n+m))=O(nm)$ time for a connected graph. Once the radius is known, the required paths, selected vertices, and ball-cover tests can all be computed in $O(n+m)$ time. Thus the overall running time of the algorithm presented here is $O(nm)$.

In fact, the running time can be improved to $O(n+m)$ by avoiding the explicit computation of the radius. Starting from an arbitrary vertex, one breadth-first search produces an isometric path $P$ whose length is at least $\rad(G)$. A second breadth-first search, rooted at a suitably chosen vertex of $P$ near its middle, produces the second isometric path $Q$. The two-path selection and the ball-cover test can then be used to give the same approximation guarantee. However, the two BFS paths need not have the same length. Handling this requires reindexing suitable subpaths and treating several additional congruence cases, which makes the corresponding lemmas more technical and may obscure the main structural idea and its interpretation. We therefore omit this refinement and retain the simpler radius-based presentation. Nevertheless, this refinement yields an $O(n+m)$-time factor-$2$ approximation algorithm for Maximum Multipacking.

Since Multipacking is NP-complete on general graphs [7], it is natural to ask whether an approximation algorithm with factor strictly below $2$ is possible in polynomial time, or whether it is tight.