cproblem[1]

#1

# Budgeted Out-tree Maximization with Submodular Prizes

Gianlorenzo D’Angelo  Gran Sasso Science Institute, L’Aquila, Italy  Esmaeil
Delfaraz  Gran Sasso Science Institute, L’Aquila, Italy  Hugo Gilbert
Université Paris-Dauphine, Université PSL, CNRS, LAMSADE, 75016 Paris, France

###### Abstract

We consider a variant of the prize collecting Steiner tree problem in which we
are given a _directed graph_ $D=(V,A)$, a monotone submodular prize function
$p:2^{V}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$, a cost function
$c:V\rightarrow\mathbb{Z}^{+}$, a root vertex $r\in V$, and a budget $B$. The
aim is to find an out-subtree $T$ of $D$ rooted at $r$ that costs at most $B$
and maximizes the prize function. We call this problem _Directed Rooted
Submodular Out-tree_ (DRSO).

For the case of undirected graphs and additive prize functions, Moss and
Rabani [SIAM J. Comput. 2007] gave an algorithm that guarantees an
$O(\log|V|)$-approximation factor if a violation by a factor 2 of the budget
constraint is allowed. Bateni et al. [SIAM J. Comput. 2018] improved the
budget violation factor to $1+\varepsilon$ at the cost of an additional
approximation factor of $O(1/\varepsilon^{2})$, for any $\varepsilon\in(0,1]$.
For directed graphs, Ghuge and Nagarajan [SODA 2020] gave a quasi-polynomial-
time $O\left(\frac{\log n^{\prime}}{\log\log n^{\prime}}\right)$-approximation
algorithm, where $n^{\prime}$ is the number of vertices in an optimal
solution, for the case in which the costs are associated to the edges.

In this paper we give a polynomial-time algorithm for DRSO that guarantees an
approximation factor of $O(\sqrt{B}/\varepsilon^{3})$ at the cost of a budget
violation of a factor $1+\varepsilon$, for any $\varepsilon\in(0,1]$. The same
result holds for the edge-cost case, to our knowledge this is the first
polynomial-time approximation algorithm for this case.

We further show that the unrooted version of DRSO can be approximated to a
factor of $O(\sqrt{B})$ without budget violation, which is an improvement over
the factor $O(\Delta\sqrt{B})$ given in [Kuo et al. IEEE/ACM Trans. Netw.
2015] for the undirected and unrooted case, where $\Delta$ is the maximum
degree of the graph. Finally, we provide some new/improved approximation
bounds for several related problems, including the additive-prize version of
DRSO, the maximum budgeted connected set cover problem, and the budgeted
sensor cover problem.

##  1 Introduction

Prize collecting Steiner tree problems (PCSTP) have been extensively studied
due to their applications in designing computer and telecommunication
networks, VLSI design, computational geometry, wireless mesh networks, and
cancer genome studies [5, 7, 14, 22, 31]. Very interesting polynomial-time
constant/poly-logarithmic approximation algorithms have been proposed for many
variants of PCSTP when the graph is undirected [1, 2, 9, 11, 17, 20, 28].
However, these problems are usually much harder on directed graphs. For
instance, there is a simple polynomial-time $2$-approximation algorithm for
the undirected Steiner tree problem, but no quasi-polynomial-time algorithm
for the directed Steiner tree problem achieving an approximation ratio of
$o\left(\frac{\log^{2}k}{\log\log k}\right)$ exists, unless
$NP\subseteq\bigcap_{0<\varepsilon<1}\text{ZPTIME}(2^{n^{\varepsilon}})$ or
the Projection Game Conjecture is false [12], where $k$ is the number of
terminal nodes.

Some of the most relevant variants of PCSTP are represented by prize
collecting problems with budget constraints. In such problems, we are usually
given a graph with prizes and costs on the nodes and the goal is to find a
tree that maximizes the sum of the prize of its nodes, while keeping the total
cost bounded by a given budget. Guha et al. [13] introduced the case in which
the graph is undirected and the goal is to find a tree containing a
distinguished vertex, called root, with the maximum prize respecting the
budget constraint, we call this problem _Undirected Rooted Additive Tree_
(URAT). They gave an algorithm that achieves an $O(\log^{2}n)$-approximation
factor, where $n$ is the number of nodes in the graph, but the computed
solution requires a factor-2 violation of the budget constraint. Moss and
Rabani [26] and Bateni et al. [2] further investigated URAT and improved the
results from the approximability point of view. The former paper improved the
approximation factor to $O(\log n)$, with the same budget violation, and the
latter one improved the budget violation factor to $1+\varepsilon$ to obtain
an approximation factor of $O\left(\frac{1}{\varepsilon^{2}}\log n\right)$,
for any $\varepsilon\in(0,1]$. Kortsarz and Nutov [21] showed that the
unrooted version of URAT, so does URAT, admits no $o(\log\log
n)$-approximation algorithm, unless $NP\subseteq
DTIME(n^{\text{polylog}(n)})$, even if the algorithm is allowed to violate the
budget constraint by a factor equal to a universal constant.

In this paper, we consider a generalization of URAT on directed graphs. We are
given a directed graph, where each node is associated with a cost, and the
prize is defined by a monotone submodular function on the subsets of nodes,
and the goal is to find an _out-tree_ (a.k.a. _out-arborescence_) rooted at a
specific vertex $r$ with the maximum prize such that the total cost of all
vertices in the out-tree is no more than a given budget. We term this problem
_Directed Rooted Submodular Out-tree_ (DRSO). A closely related problem,
called _Submodular Tree Orienteering_ (STO), has been recently introduced by
Ghuge and Nagarajan [10]. STO is the same problem as DRSO except that edges
and not nodes have costs. They provided a tight quasi-polynomial-time
$O(\frac{\log n^{\prime}}{\log\log n^{\prime}})$-approximation algorithm that
requires $(n\log B)^{O(\log^{1+\varepsilon}n^{\prime})}$ time, where
$n^{\prime}$ is the number of vertices in an optimal solution and $B$ is the
budget constraint.

#### Contribution.

By extending some ideas of Kuo et al. [22] and Bateni et al. [2], we design a
polynomial-time $O(\sqrt{B}/\varepsilon^{3})$-approximation algorithm for
DRSO, violating the budget constraint $B$ by a factor of at most
$1+\varepsilon$, for any $\varepsilon\in(0,1]$ (Section 4). Our technique can
be used to obtain the same result for STO (Section 6). To our knowledge, this
is the first polynomial-time approximation algorithm for STO. We also show
that, for any $1+\varepsilon$ budget violation, with $\varepsilon\in(0,1]$,
our approach provides an $O(\sqrt{B}/\varepsilon^{2})$-approximation algorithm
for the special cases of DRSO and STO where the prize function is additive
(Section 7). We also consider the unrooted version of DRSO and give an
$O(\sqrt{B})$-approximation algorithm without budget violation (Section 5),
which is an improvement over the factor $O(\Delta\sqrt{B})$ [22] for the
undirected and unrooted version of DRSO, where $\Delta$ is the maximum degree
of the graph.

Finally we study some variants of DRSO on undirected graphs. We show that, for
any $1+\varepsilon$ budget violation, URAT admits an
$O(\Delta/\varepsilon^{2})$-approximation algorithm, while its quota version
admits a $2\Delta$-approximation algorithm. Next, we present some
approximation results for some variants of the connected maximum coverage
problem, which improve over the bounds given by Ran et al. [29]. Finally, we
provide two approximation algorithms for the Budgeted Sensor Cover problem,
which result in an improvement to the literature [22, 29, 32, 33]. We discuss
these results in Section 7.

#### Related Work.

Many variants of Prize collecting Steiner Tree problems have been
investigated. Here we list those that are more closely related to our study.
Further related work is reported in the Appendix.

Kuo et al. [22] studied the unrooted version of DRSO on undirected graphs
called _Maximum Connected Submodular function with Budget constraint_ (MCSB).
They provided an $O(\Delta\sqrt{B})$-approximation algorithm for MCSB, where
$\Delta$ is the maximum degree of the graph. Vandin et al. [31] provided a
$(\frac{2e-1}{e-1}r)$-approximation algorithm for a special case of the same
problem, where $r$ is the radius of an optimal solution. This problem
coincides with the connected maximum coverage problem in which each set has
cost one. Ran et al. [29] presented an $O(\Delta\log{n})$-approximation
algorithm for a special case of the connected maximum coverage problem.
Hochbaum and Rao [14] investigated MCSB in which each vertex costs $1$ and
provided an approximation algorithm with factor
$\min\\{1/((1-1/e)(1/R-1/B)),B\\}$, where $R$ is the radius of the graph. Chen
et al. [4] investigated the edge-cost version of MCSB. One of the applications
of MCSB is a problem in wireless sensor networks called _Budgeted Sensor Cover
Problem_ (BSCP), where the goal is to find a set of $B$ connected sensors to
maximize the number of covered users, for a given $B$. Kuo et al. [22]
provided a $5(\sqrt{B}+1)/(1-1/e)$-approximation algorithm for BSCP, which was
improved by Xu et al. [32] to $\lfloor\sqrt{B}\rfloor/(1-1/e)$. Huang et al.
[16] proposed a $8(\lceil 2\sqrt{2}C\rceil+1)^{2}/(1-1/e)$-approximation
algorithm for BSCP, where $C=O(1)$. Gao et al. [7] presented two approximation
algorithms with factors $O(\log{n})$ and $O(\sqrt{B})$ for a closely related
problem.

Johnson et al. [17] introduced an edge-cost variant of DRSO on undirected
graphs, where the prize function is additive, called E-URAT. They showed that
there exists a $(5+\varepsilon)$-approximation algorithm for the unrooted
version of E-URAT using Garg’s $3$-approximation algorithm [8] for the $k$-MST
problem, and observed that a $2$-approximation for $k$-MST would lead to a
3-approximation for E-URAT. This observation along with the Garg’s
$2$-approximation algorithm [9] for $k$-MST yield a $3$-approximation
algorithm for the unrooted version of E-URAT. Recently, Paul et al. [28]
provided a polynomial-time $2$-approximation algorithm for E-URAT.

##  2 Notation and problem statement

For an integer $k$, let $[k]:=[1,\ldots,k]$. A directed path is a directed
graph made of a sequence of distinct vertices $(v_{1},\dots,v_{k})$ and a
sequence of directed edges $(v_{i},v_{i+1})$, $i\in[k-1]$. An _out-tree_
(a.k.a. out-arborescence) is a directed graph in which there is exactly one
directed path from a specific vertex $r$, called _root_ , to each other
vertex. If a subgraph $T$ of a directed graph $D$ is an out-tree, then we say
that $T$ is an out-tree of $D$.

Let $D=(V,A)$ be a directed graph with $n$ nodes,
$c:V\rightarrow\mathbb{Z}^{+}$ be a cost function on nodes,
$p:2^{V}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ be a monotone submodular prize
function on the subsets of nodes, $r\in V$ be a root vertex, and $B$ be an
integer budget. For any subgraph $D^{\prime}$ of $D$, we denote by
$V(D^{\prime})$ and $A(D^{\prime})$ the set of nodes and edges in
$D^{\prime}$, respectively. Given $S\subseteq V$, we denote the cost of $S$ by
$c(S)=\sum_{v\in S}c(v)$ and we use shortcuts $c(D^{\prime})=c(V(D^{\prime}))$
and $p(D^{\prime})=p(V(D^{\prime}))$ for a subgraph $D^{\prime}$ of $D$. In
the Directed Rooted Submodular Out-tree problem (DRSO), the goal is to find an
out-tree $T$ of $D$ rooted at $r$ such that $c(T)\leq B$ and $p(T)$ is
maximum. Throughout the paper, we denote an optimal solution to DRSO by
$T^{*}$.

Given two nodes $u$ and $v$ in $V$, a path in $D$ from $u$ to $v$ with the
minimum cost is called a shortest path and its cost, denoted by $dist(u,v)$,
is called the distance from $u$ to $v$ in $D$.

An algorithm is a bicriteria $(\beta,\alpha)$-approximation algorithm for DRSO
if, for any instance $I$ of the problem, it returns a solution $Sol_{I}$ such
that $p(Sol_{I})\geq\frac{OPT_{I}}{\alpha}$ and $c(Sol_{I})\leq\beta B$, where
$OPT_{I}$ is the optimum for $I$.

##  3 Results and Techniques

Our main result is:

######  Theorem 3.1.

DRSO admits a polynomial-time bicriteria
$\left(1+\varepsilon,O\left(\frac{\sqrt{B}}{\varepsilon^{3}}\right)\right)$-approximation
algorithm, for any $\varepsilon\in(0,1]$.

Our approach combines and extends techniques given by Kuo et al. [22] and
Bateni et al. [2]. To illustrate our techniques, we now consider the case in
which costs are unitary, i.e. $c(v)=1$, for each $v\in V$, and the prize
function is additive, i.e. $p(S)=\sum_{v\in S}p(\\{v\\})$, for any $S\subseteq
V$. In this case, the distance from a node $u$ to a node $v$ is equal to the
minimum number of nodes in a path from $u$ to $v$ and the cost of a tree $T$
is equal to its size, $c(T)=|V(T)|$. W.lo.g. we also assume that the distance
from $r$ to any node is at most $B$. We will give the proof for the general
case in Section 4.

The algorithm works as follows. For any vertex $u$, we denote as $V_{u}$ the
set of all nodes that are at a distance no more than $\lfloor\sqrt{B}\rfloor$
from $u$, $V_{u}:=\\{v~{}|~{}dist(u,v)\leq\lfloor\sqrt{B}\rfloor\\}$. We first
select a subset $S_{u}$ of $V_{u}$ of at most $\lfloor\sqrt{B}\rfloor$ nodes
with the maximum prize, $S_{u}:=\arg\max\\{p(S)~{}:~{}S\subseteq
V_{u},|S|\leq\lfloor\sqrt{B}\rfloor\\}$.111This step can be done in polynomial
time since function $p$ is additive. If $p$ is monotone and submodular this
step consists in solving the submodular maximization problem. See Section 4
for more details. We then compute a minimal inclusion-wise out-tree $T_{u}$
rooted at $u$ that spans all nodes in $S_{u}$. Note that $|V(T_{u})|\leq B$
since the distance from $u$ to any node in $S_{u}$ is at most
$\lfloor\sqrt{B}\rfloor$. Let $z$ be a node such that $p(T_{z})$ is maximum.
If $z=r$, then we take $T_{z}$ as our solution, otherwise we compute a
solution by adding to $T_{z}$ a shortest path $P$ from $r$ to $z$ and removing
the edges in $A(T_{z})\setminus A(P)$ incoming the nodes in $V(T_{z})\cap
V(P)$. Let $T$ be our solution and $T^{*}$ be an optimal solution.

We will prove (Lemma 4.3) that any out-tree $\hat{T}$ can be covered by at
most $N=O(|\hat{T}|/m)$ out-subtrees $\\{\hat{T}_{i}\\}_{i=1}^{N}$ with at
most $m$ nodes each, where $m$ is any positive integer less than $|\hat{T}|$.
By applying this claim to an optimal solution $T^{*}$ and by setting
$m=\lfloor\sqrt{B}\rfloor$, we obtain

$p(T^{*})=p\left(\bigcup_{i=1}^{N}V(T^{*}_{i})\right)\leq Np(T^{\prime}),$

where $p(T^{\prime})=\max\\{p(T^{*}_{i})~{}|~{}i\in[N]\\}$,
$|T^{\prime}|\leq\lfloor\sqrt{B}\rfloor$, and $N=O(|T^{*}|/m)=O(\sqrt{B})$.
Let $w$ be the root of $T^{\prime}$. Recall that $S_{w}$ is a set of at most
$\lfloor\sqrt{B}\rfloor$ nodes that are at a distance no more than
$\lfloor\sqrt{B}\rfloor$ from $w$ and have the maximum prize and $T_{w}$
contains all the nodes in $S_{w}$. Since
$|T^{\prime}|\leq\lfloor\sqrt{B}\rfloor$, we have

$p(T^{\prime})\leq p(S_{w})\leq p(T_{w})\leq p(T_{z})\leq p(T).$

Since $N=O(\sqrt{B})$, we conclude that $p(T^{*})=O(\sqrt{B})p(T)$.

Note that the cost of $T$ is upper-bounded by $2B$, as both the cost of
$T_{z}$ and that of a shortest path from $r$ to $z$ are at most $B$. We can
use the trimming procedure introduced by Bateni et al. [2] to obtain an out-
subtree of $T$ with cost at most $(1+\varepsilon)B$ by loosing an
approximation factor of $O(1/\varepsilon^{2})$, for any $\varepsilon\in(0,1]$
(see Lemma B.1). This shows Theorem 3.1 for the unit-cost, additive-prize
case. In the case in which the prize is a general monotone submodular
function, the trimming procedure by Bateni et al. cannot be applied. We show
how to generalize this procedure to the case of any monotone submodular prize
function by loosing an extra approximation factor of $O(1/\varepsilon)$.

We can use the same approach to obtain a polynomial-time bicriteria
$\left(1+\varepsilon,O\left(\frac{\sqrt{B}}{\varepsilon^{2}}\right)\right)$-approximation
algorithm for the case of additive prize function and edge-cost. More
importantly, we can obtain a polynomial-time bicriteria
$\left(1+\varepsilon,O\left(\frac{\sqrt{B}}{\varepsilon^{3}}\right)\right)$-approximation
algorithm for STO, i.e. for the edge-cost case where the prize function is
monotone submodular. To the best of our knowledge, this is the first
polynomial-time approximation algorithm for STO.

Finally, for the unrooted version the same approach with some minor changes
achieves an $O(\sqrt{B})$-approximation with no budget violation.

##  4 Approximation Algorithm for DRSO

We now introduce our polynomial-time approximation algorithm for DRSO. We
start by defining a procedure that takes as input an out-tree of a directed
graph $D$ and returns another out-tree of $D$ which has a smaller cost but
preserves the same prize-to-cost ratio (up to a bounded multiplicative
factor).

Bateni et al. [2] introduced a similar procedure for the case of undirected
graphs and additive prize function. In their case, we are given an undirected
graph $G=(V,E)$, a distinguished vertex $r\in V$ and a budget $B$, where each
vertex $v\in V$ is assigned with a prize $p^{\prime}(v)$ and a cost
$c^{\prime}(v)$. For a tree $T$, the prize and cost of $T$ are the sum of the
prizes and costs of the nodes of $T$ and are denoted by $p^{\prime}(T)$ and
$c^{\prime}(T)$, respectively. A graph $G$ is called _$B$ -proper_ for the
vertex $r$ if the cost of reaching any vertex from $r$ is at most $B$. Bateni
et al. proposed a trimming process that leads to the following lemma.

######  Lemma 4.1 (Lemma 3 in [2]).

Let $T$ be a tree rooted at $r$ with the prize-to-cost ratio
$\gamma=\frac{p^{\prime}(T)}{c^{\prime}(T)}$. Suppose the underlying graph is
$B$-proper for $r$ and for $\varepsilon\in(0,1]$ the cost of the tree is at
least $\frac{\varepsilon B}{2}$. One can find a tree $T^{\prime}$ containing
$r$ with the prize-to-cost ratio at least $\frac{\varepsilon\gamma}{4}$ such
that $\varepsilon B/2\leq c^{\prime}(T^{\prime})\leq(1+\varepsilon)B$.

We now generalize this trimming process to the case in which the underlying
graph is directed and the prize function is monotone and submodular by
borrowing ideas from [2].

We introduce some additional definitions. Let $T$ be an out-tree rooted at
$r$. A _full_ out-subtree of $T$ rooted at some node $v$ is an out-subtree of
$T$ containing all the vertices that are reachable from $r$ through $v$ in
$T$. The set of _strict_ out-subtrees of $T$ is the set of all full out-
subtrees of $T$ other than $T$ itself. The set of _immediate_ out-subtrees of
$T$ is the set of all full out-subtrees rooted at the children of $r$ in $T$.
A directed graph $D=(V,A)$ is $B$-_appropriate_ for a node $r$ if
$dist(r,v)\leq B$ for any node $v\in V$.

######  Lemma 4.2.

Let $D=(V,A)$ be a $B$-appropriate graph for a node $r$. Let $T$ be an out-
tree of $D$ rooted at $r$ with the prize-to-cost ratio
$\gamma=\frac{p(T)}{c(T)}$, where $p$ is a monotone submodular function.
Suppose that $\frac{\varepsilon B}{2}\leq c(T)\leq hB$, where $h>1$ and
$\varepsilon\in(0,1]$. One can find an out-subtree $\hat{T}$ rooted at $r$
with the prize-to-cost ratio at least $\frac{\varepsilon^{2}\gamma}{32h}$ such
that $\varepsilon B/2\leq c(\hat{T})\leq(1+\varepsilon)B$.

###### Proof.

We run the following initial trimming procedure. We iteratively remove a
strict out-subtree $T^{\prime}$ from $T$ that satisfies two conditions: (i)
the prize-to-cost ratio of $T\setminus T^{\prime}$ is at least $\gamma$, and
(ii) $c(T\setminus T^{\prime})\geq\frac{\varepsilon}{2}B$. We repeat this
process until no such strict out-subtree exists. Let $T_{-}$ be the remaining
out-tree after applying this process on $T$.

Now if $c(T_{-})\leq(1+\varepsilon)B$, the desired out-subtree is obtained.
Suppose it is not the case. A full out-subtree $T^{\prime}$ is called _rich_
if $c(T^{\prime})\geq\frac{\varepsilon}{2}B$ and the prize-to-cost ratio of
$T^{\prime}$ and all its strict out-subtrees are at least $\gamma$. We claim
that if there exists a rich out-subtree, then we can find the desired out-
subtree $\hat{T}$.

######  Claim 4.1.

Given a rich out-subtree $T^{\prime}$, the desired out-subtree $\hat{T}$ can
be found.

###### Proof.

We first find a rich out-subtree $T^{\prime\prime}$ of $T^{\prime}$ such that
the strict out-subtrees of $T^{\prime\prime}$ are not rich, i.e.,
$c(T^{\prime\prime})\geq\frac{\varepsilon}{2}B$ while the cost of any strict
out-subtree of $T^{\prime\prime}$ (if any exist) is less than
$\frac{\varepsilon}{2}B$. Let $C$ be the total cost of the immediate out-
subtrees of $T^{\prime\prime}$. We distinguish between two cases:

  1. 1.

If $C<\frac{\varepsilon}{2}B$, then let $\hat{T}$ be the union of
$T^{\prime\prime}$ and a shortest path $P$ from $r$ to the root
$r^{\prime\prime}$ of $T^{\prime\prime}$. $\hat{T}$ has cost at most
$C+B\leq(1+\varepsilon)B$ and prize at least $\gamma(\frac{\varepsilon}{2}B)$.
This implies that $\hat{T}$ has ratio at least
$\frac{\gamma\varepsilon}{2(1+\varepsilon)}\geq\frac{\gamma\varepsilon}{4}\geq\frac{\gamma\varepsilon^{2}}{32h}$.

  2. 2.

If $C\geq\frac{\varepsilon}{2}B$, we proceed as follows. Since each immediate
out-subtree of $T^{\prime\prime}$ has a cost strictly smaller than
$\frac{\varepsilon}{2}B$, we can partition all the immediate out-subtrees of
$T^{\prime\prime}$ into $M$ groups $S_{1},\dots,S_{M}$ in such a way that the
total cost of immediate out-subtrees in each group $S_{i}$ is at least
$\frac{\varepsilon}{2}B$ and at most $\varepsilon B$. We can always group in
this way since the cost of each immediate out-subtree of $T^{\prime\prime}$ is
less than $\frac{\varepsilon}{2}B$ while $C\geq\frac{\varepsilon}{2}B$. Since
the total cost of all the immediate out-subtrees of $T^{\prime\prime}$ is
upper bounded by $hB$, then the number of selected groups $M$ is at most

$M\leq\left\lceil\frac{hB}{\frac{\varepsilon}{2}B}\right\rceil=\left\lceil\frac{2h}{\varepsilon}\right\rceil\leq\left\lfloor\frac{2h}{\varepsilon}\right\rfloor+1\leq\left\lfloor\frac{4h}{\varepsilon}\right\rfloor\leq\frac{4h}{\varepsilon}.$

We now add the root $r^{\prime\prime}$ of $T^{\prime\prime}$ to each group
$S_{i}$ and denote the new group by $S^{\prime}_{i}$, i.e.,
$S^{\prime}_{i}=S_{i}\cup\\{r^{\prime\prime}\\}$, for any $i\in[M]$. By the
monotonicity and submodularity of $p$, we have
$\sum_{i=1}^{M}p(S^{\prime}_{i})\geq
p(S^{\prime}_{1})+\sum_{i=2}^{M}p(S_{i})\geq
p(S^{\prime}_{1}\cup\bigcup_{i=2}^{M}S_{i})=p(T^{\prime\prime})$. Now among
$S^{\prime}_{1},\dots,S^{\prime}_{M}$, we select the group $S^{\prime}_{z}$
that maximizes the prize, i.e., $z=\arg\max_{i\in[M]}p(S^{\prime}_{i})$. We
know that

$p(S^{\prime}_{z})\geq\frac{1}{M}\sum_{i=1}^{M}p(S^{\prime}_{i})\geq\frac{p(T^{\prime\prime})}{M}=\frac{\varepsilon}{4h}p(T^{\prime\prime})\geq\frac{\varepsilon}{4h}\cdot\frac{\gamma\varepsilon}{2}B=\frac{\gamma\varepsilon^{2}}{8h}B.$

Finally, let $\hat{T}$ be the union of a shortest path $P$ from $r$ to
$r^{\prime\prime}$, $S^{\prime}_{z}$, and the edges from $r^{\prime\prime}$ to
the roots of the out-subtrees in $S_{z}$ (see Figure 1). By monotonicity,
$\hat{T}$ has the total prize at least $p(\hat{T})\geq
p(S^{\prime}_{z})\geq\frac{\gamma\varepsilon^{2}}{8h}B$. Note that
$c(\hat{T})\leq(1+\varepsilon)B$ as
$c(S^{\prime}_{z}\setminus\\{r^{\prime\prime}\\})=c(S_{z})\leq\varepsilon B$
and the shortest path from $r$ to $r^{\prime\prime}$ costs at most $B$ (since
the graph is $B$-appropriate). This implies that the prize-to-cost ratio of
$\hat{T}$ is at least
$\frac{\gamma\varepsilon^{2}}{8h(1+\varepsilon)}\geq\frac{\gamma\varepsilon^{2}}{16h}\geq\frac{\gamma\varepsilon^{2}}{32h}$.∎

$r$$r^{\prime\prime}$……………$S_{z}$$T^{\prime\prime}$$T^{\prime}$

Figure 1: $T_{-}$ is rooted at $r$, which is the whole out-tree. The green
dashed closed curve represents the rich out-subtree $T^{\prime}$. The orange
circle represents $T^{\prime\prime}$ rooted at $r^{\prime\prime}$, where its
strict out-subtrees are not rich, i.e., the cost of any strict out-subtree of
$T^{\prime\prime}$ is less than $\frac{\varepsilon}{2}B$. The blue dashed
circle represents the partition $S_{z}$, which maximizes the prize and costs
at most $\varepsilon B$. The red out-subtree represents $\hat{T}$, which is
the union of a shortest path from $r$ to $r^{\prime\prime}$, $S_{z}$ and the
edges from $r^{\prime\prime}$ to the immediate out-subtrees of
$T^{\prime\prime}$ in $S_{z}$. Note that for the sake of simplicity, in this
figure we suppose that the shortest path from $r$ to $r^{\prime\prime}$ is
included in $T_{-}$.

It only remains to consider the case when there is no reach out-subtree. Since
$T_{-}$ is not reach and $c(T_{-})\geq\frac{\varepsilon}{2}B$, the ratio of at
least one strict out-subtree of $T_{-}$ is less than $\gamma$. Now we find a
strict out-subtree $T^{\prime}$ with ratio less than $\gamma$ such that the
ratio of all of its strict out-subtrees (if any exist) is at least $\gamma$.
We first need to show that $c(T_{-}\setminus
T^{\prime})<\frac{\varepsilon}{2}B$.

######  Claim 4.2.

$c(T_{-}\setminus T^{\prime})<\frac{\varepsilon}{2}B$.

###### Proof.

By the submodularity of $p$, we know that $p(T_{-}\setminus
T^{\prime})+p(T^{\prime})\geq p(T_{-})$. This implies that

$\displaystyle\frac{p(T_{-}\setminus T^{\prime})}{c(T_{-}\setminus
T^{\prime})}\geq\frac{p(T_{-})-p(T^{\prime})}{c(T_{-})-c(T^{\prime})}.$ (1)

Let $\gamma^{\prime}=\frac{p(T^{\prime})}{c(T^{\prime})}$ be the prize-to-cost
ratio of $T^{\prime}$. We know that

$\displaystyle
p(T_{-})-p(T^{\prime})=c(T_{-})\gamma-c(T^{\prime})\gamma^{\prime}>c(T_{-})\gamma-c(T^{\prime})\gamma,$
(2)

where the inequality holds because $\gamma^{\prime}<\gamma$. By Equations (1)
and (2), we have $\frac{p(T_{-}\setminus T^{\prime})}{c(T_{-}\setminus
T^{\prime})}>\gamma$. As the prize-to-cost ratio of $T_{-}\setminus
T^{\prime}$ is more than $\gamma$ but $T^{\prime}$ has not been removed from
$T$ during the initial phase, then $c(T_{-}\setminus
T^{\prime})<\frac{\varepsilon}{2}B$. This concludes the claim. ∎

We know that $c(T_{-})>(1+\varepsilon)B$ and the cost from $r$ to the root of
$T^{\prime}$ is at most $B$. Then by Claim 4.2, the total cost of immediate
out-subtrees of $T^{\prime}$ is at least $\frac{\varepsilon}{2}B$. Also, the
cost of an immediate out-subtree of $T^{\prime}$ is less than
$\frac{\varepsilon}{2}B$, otherwise we have a rich out-subtree. As the ratio
and cost of $T_{-}$ are at least $\gamma$ and $\frac{\varepsilon}{2}B$,
respectively, then $p(T_{-})\geq\frac{\gamma\varepsilon}{2}B$. Now we
distinguish between two cases:

  1. 1.

If $p(T^{\prime})\geq\frac{\gamma\varepsilon}{4}B$, by similar reasoning as
above, we group the immediate out-subtrees of $T^{\prime}$ into $M$ groups
$S_{1},\dots,S_{M}$ such that each group costs at least $\frac{\varepsilon
B}{2}$ and at most $\varepsilon B$. Now define a new group
$S^{\prime}_{i}=S_{i}\cup\\{r^{\prime}\\}$, for any $i\in[M]$. Let
$z=\arg\max_{i\in[M]}p(S^{\prime}_{i})$. Then the group $S^{\prime}_{z}$,
which maximizes the prize is selected. We know that
$M\leq\frac{4h}{\varepsilon}$. Hence,

$p(S^{\prime}_{z})\geq\frac{\varepsilon}{4h}p(T^{\prime})\geq\frac{\varepsilon}{4h}\cdot\frac{\gamma\varepsilon}{4}B=\frac{\gamma\varepsilon^{2}}{16h}B$

Let $\hat{T}$ be the union of a shortest path $P$ from $r$ to $r^{\prime}$,
$S^{\prime}_{z}$, and the edges from $r^{\prime}$ to the roots of the out-
subtrees in $S_{z}$. The cost of $\hat{T}$ is at most $(1+\varepsilon)B$ and
the prize-to-cost ratio is at least
$\frac{\gamma\varepsilon^{2}}{16h(1+\varepsilon)}\geq\frac{\gamma\varepsilon^{2}}{32h}$.

  2. 2.

If $p(T^{\prime})<\frac{\gamma\varepsilon}{4}B$, we proceed as follows.
Consider the out-subtree $T^{\prime\prime}=T_{-}\setminus T^{\prime}$, which
is rooted at $r$. Recall that by Claim 4.2, we have
$c(T^{\prime\prime})<\frac{\varepsilon}{2}B$. We connect a subset of immediate
out-subtrees $T^{\prime}_{1},\dots,T^{\prime}_{q}$ of $T^{\prime}$ with cost
$\frac{\varepsilon}{2}B-c(T^{\prime\prime})\leq
c(\bigcup_{i=1}^{q}T^{\prime}_{i})\leq\varepsilon B-c(T^{\prime\prime})$ to
the root of $T^{\prime\prime}$ through the root of $T^{\prime}$. Since the
cost of each immediate out-subtree of $T^{\prime}$ is less than
$\frac{\varepsilon}{2}B$ (otherwise we have a rich out-subtree) and
$c(T^{\prime})>(1+\frac{\varepsilon}{2})B$, a subset of immediate out-subtrees
$T^{\prime}_{1},\dots,T^{\prime}_{q}$ of $T^{\prime}$ with such a cost can be
found. We call the resulting out-subtree $\hat{T}$ and observe that
$c(\hat{T})\geq\frac{\varepsilon}{2}B$ (see Figure 2). We now bound the prize-
to-cost ratio of $\hat{T}$. First note that by the submodularity of $p$,
$p(T^{\prime\prime})+p(T^{\prime})\geq p(T_{-})$. Thus by the subcase
assumption and the monotonicity of $p$, we have $p(\hat{T})\geq
p(T^{\prime\prime})\geq\frac{\gamma\varepsilon}{4}B$. Since
$\frac{\varepsilon}{2}B-c(T^{\prime\prime})\leq
c(\bigcup_{i=1}^{q}T^{\prime}_{i})\leq\varepsilon B-c(T^{\prime\prime})$ and
the graph is $B$-appropriate, $c(\hat{T})\leq(1+\varepsilon)B$. Therefore, the
prize-to-cost ratio of the resulting out-subtree $\hat{T}$ is
$\frac{\gamma\varepsilon}{4(1+\varepsilon)}\geq\frac{\gamma\varepsilon}{8}\geq\frac{\gamma\varepsilon^{2}}{32h}$.

$r$$r^{\prime}$……………$\bigcup_{i=1}^{q}T^{\prime}_{i}$$T^{\prime}$$T^{\prime\prime}$

Figure 2: $T_{-}$ is rooted at $r$, which is the whole out-tree. The green
dashed circle represents $T^{\prime\prime}$ rooted at $r$. The orange circle
represents $T^{\prime}$ rooted at $r^{\prime}$, where its cost is more than
$(1+\frac{\varepsilon}{2})B$. The blue dashed circle represents a subset of
immediate out-subtrees $T^{\prime}_{1},\dots,T^{\prime}_{q}$ of $T^{\prime}$
with cost $\frac{\varepsilon}{2}B-c(T^{\prime\prime})\leq
c(\bigcup_{i=1}^{q}T^{\prime}_{i})\leq\varepsilon B-c(T^{\prime\prime})$. The
red out-subtree represents $\hat{T}$, which is the union of
$T^{\prime\prime}$, the edge from $T^{\prime\prime}$ to $r^{\prime}$,
$\bigcup_{i=1}^{q}T^{\prime}_{i}$ and the edges from $r^{\prime}$ to
$T^{\prime}_{1},\dots,T^{\prime}_{q}$.

The proof is complete. ∎

To propose our algorithm, we need a last element. Let
$U=\\{x_{1},\dots,x_{n}\\}$ be a ground set, $c:U\rightarrow Z^{+}$ be a cost
function, $f:2^{U}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ be a monotone
submodular function, and $K$ be an integer budget. In the Submodular
Maximization problem (SM), we are looking for a subset $S\subseteq U$ such
that $|S|\leq K$ and $f(S)$ is maximum. Nemhauser et al. [27] provided a
greedy algorithm that starts from $S:=\emptyset$ and runs $K$ iterations in
which, at each iteration, it adds to $S$ the element $x$ which maximizes
$f(S\cup\\{x\\})-f(S)$. This algorithm guarantees a $(1-e^{-1})$-approximation
for SM. We denote by RSM the rooted variant of SM in which, additionally, a
specific element $v\in U$ is required to be included in the solution, that is
we are looking for a subset $S\subseteq U$ such that $|S|\leq K$, $v\in S$ and
$f(S)$ is maximum. We can run Nemhauser et al. [27]’s approach for RSM with a
minor change: we initialize $S:=\\{v\\}$ and run $K-1$ greedy iterations. We
call this approach Greedy. It can be shown that Greedy guarantees a
$(1-e^{-1})$-approximation algorithm for RSM (see e.g. [22]).

Now we can propose our approximation algorithm for DRSO, which is reported in
Algorithm 1.

Input: Directed graph $D=(V,A)$; monotone submodular prize function
$p:2^{V}\rightarrow\mathbb{R}^{+}\cup\\{0\\}$; cost function
$c:V\rightarrow\mathbb{Z}^{+}$; root $r\in V$; budget $B$; and
$\varepsilon^{\prime}\in(0,1]$.

Output: Out-tree $T$ of $D$ rooted at $r$ such that
$c(T)\leq(1+\varepsilon^{\prime})B$.

1: Remove from $D$ all the nodes at a distance more than $B$ from $r$;

2: for $u\in V$ do

3: $V_{u}:=\\{v~{}|~{}dist(u,v)\leq c(u)+\lfloor\sqrt{B}\rfloor\\}$;

4: Define an instance $I^{RSM}_{u}$ of RSM with elements $V_{u}$, specific
element $u$, budget $\lfloor\sqrt{B}\rfloor+1$, profits $p(S)$, for each
$S\subseteq V_{u}$;

5: Let $S_{u}$ be a $(1-e^{-1})$-approximate solution to $I^{RSM}_{u}$,
computed by using Greedy;

6: Let $T_{u}$ be a minimal inclusion-wise out-tree rooted at $u$ spanning all
nodes in $S_{u}$;

7: end for

8: $z:=\arg\max_{u\in V}p(T_{u})$;

9: Let $P$ be a shortest path from $r$ to $z$;

10: $T:=P\cup T_{z}$;

11: $A(T):=A(T)\setminus\\{(v,w)\in A(T_{z})\setminus A(P)~{}:~{}w\in
V(T_{z})\cap V(P)\\}$;

12: Apply the trimming process in Lemma 4.2 with
$\varepsilon=\varepsilon^{\prime}$ to $T$;

13: return $T$.

Algorithm 1

In words, Algorithm 1 first computes the maximal inclusion-wise
$B$-appropriate subgraph for $r$ of a given graph $D$ by removing all the
nodes at a distance larger than $B$ from $r$. Let $D=(V,A)$ be the resulting
directed graph. For each node $u$, it computes the set $V_{u}$ of all nodes
that are at a distance no more than $c(u)+\lfloor\sqrt{B}\rfloor$ from $u$.
Let $S^{*}_{u}$ be a subset of $V_{u}$ such that
$|S^{*}_{u}|\leq\lfloor\sqrt{B}\rfloor+1$, $u\in S^{*}_{u}$, and
$p(S^{*}_{u})$ is maximum. Finding $S^{*}_{u}$ requires to solve an instance
$I^{RSM}_{u}$ of RSM where the elements are $V_{u}$, the budget is
$\lfloor\sqrt{B}\rfloor+1$, the specific element is $u$, and profits are
defined by function $p(\cdot)$. Using Greedy, Algorithm 1 computes in
polynomial time an approximate solution $S_{u}$ to $I^{RSM}_{u}$ with $u\in
S_{u}$, $|S_{u}|\leq\lfloor\sqrt{B}\rfloor+1$ and
$p(S_{u})\geq(1-e^{-1})p(S^{*}_{u})$. Finally, for each $u\in V$, Algorithm 1
computes a spanning out-tree $T_{u}$ rooted in $u$ that spans all the nodes in
$S_{u}$. Let $z$ be a node such that $p(T_{z})$ is maximum, i.e.,
$z=\arg\max_{u\in V}p(T_{u})$. Then, we have $c(T_{z}\setminus\\{z\\})\leq B$
as $|S_{z}\setminus\\{z\\}|\leq\lfloor\sqrt{B}\rfloor$ and $dist(z,v)\leq
c(z)+\lfloor\sqrt{B}\rfloor$ for any $v\in S_{z}$. If $z=r$, then Algorithm 1
defines $T=T_{z}$. Otherwise, it computes a shortest path $P$ from $r$ to $z$
and defines $T$ as the union of $T_{z}$ and $P$. Since the obtained graph
might not be an out-tree, Algorithm 1 removes the possible edges incoming the
nodes in $V(T_{z})\cap V(P)$ that belong only to $T_{z}$. The obtained out-
tree $T$ has a cost of at most $2B$ as $dist(r,z)\leq B$ and
$c(T_{z}\setminus\\{z\\})\leq B$. Therefore, Algorithm 1 applies the trimming
process in Lemma 4.2 to $T$ to reduce the cost to $(1+\varepsilon)B$, where
$\varepsilon\in(0,1]$ and outputs the resulting out-tree.

In the next theorem, we show that Algorithm 1 guarantees a bicriteria
approximation.

See 3.1

For our analysis we need to decompose an optimal out-tree into a bounded
number of out-subtrees of bounded cost as in the following lemma, which is
similar to Claim 3 in Kuo et al. [22] on the unrooted problem and undirected
graphs.

######  Lemma 4.3.

For any out-tree $\hat{T}=(V,A)$ rooted at $r$ with cost $c(\hat{T})$ and any
$m\leq c(\hat{T})$, there exist $N\leq 5\lfloor\frac{c(\hat{T})}{m}\rfloor$
out-subtrees $T^{i}=(V^{i},A^{i})$ of $\hat{T}$, for $i\in[N]$, where
$V^{i}\subseteq V$, $A^{i}=(V^{i}\times V^{i})\cap A$, $c(V^{i})\leq
m+c(r_{i})$, $r_{i}$ is the root of $T^{i}$, and $\bigcup_{i=1}^{N}V^{i}=V$.

###### Proof.

An out-subtree $T^{\prime}$ of $\hat{T}$ rooted at $r^{\prime}$ is called
feasible if $c(V(T^{\prime})\setminus\\{r^{\prime}\\})\leq m$; it is called
_infeasible_ otherwise.

Let us consider the following procedure called Proc. Proc takes as input an
out-tree $T^{\prime}$, Proc$(T^{\prime})$, and visits the vertices on
$T^{\prime}$ from the leaves to the root. In this visiting process when Proc
encounters a vertex $v$ such that $T^{\prime}_{v}$ is the first infeasible
full out-subtree, it removes $T^{\prime}_{v}$ from $T^{\prime}$, i.e.,
$T^{\prime}=T^{\prime}\setminus T^{\prime}_{v}$. Proc iteratively repeats this
process for the new tree $T^{\prime}$. Finally, Proc returns all infeasible
full out-subtrees that have been found in the visit.

Let $I_{1},\dots,I_{s}$ be the set of all infeasible full out-subtrees that
have been returned after running Proc$(\hat{T})$ and let $I_{s+1}$ be the
possible feasible out-subtree rooted at $r$ that remains after the visit of
Proc$(\hat{T})$. We have $\cup_{i\in[s+1]}V(I_{i})=V(\hat{T})$ and
$V(I_{i})\cap V(I_{j})=\emptyset$, for $i\neq j$.

For each $i\in[s]$, let us consider the infeasible out-subtree $I_{i}$, let
$v_{i}$ be the root of $I_{i}$, and let $I_{u}$ be the full out-subtree of
$I_{i}$ rooted at $u$, for each child $u$ of $v_{i}$. Each out-subtree $I_{i}$
is further divided into out-subtrees as follows:

  * •

for all children $u$ of $v_{i}$ such that $c(I_{u})\geq m/2$, we generate an
out-subtree $I_{u}$, observe that $c(I_{u})\leq m+c(u)$ because $I_{u}$ is
feasible. If all the children of $v_{i}$ are in this category, we generate a
further out-subtree made of only node $v_{i}$.

  * •

All children $u$ of $v_{i}$ such that $c(I_{u})<m/2$ are partitioned into
groups of cost between $m/2$ and $m$, plus a possible group of cost smaller
then $m/2$. Note that it is always possible to partition the nodes in this way
because $c(I_{u})<m/2$ for all such nodes. Then, for each of these groups, we
generate an out-subtree by connecting $v_{i}$ to the roots of the out-subtrees
in the group. Note that all the generated out-subtrees have the same root
$v_{i}$ and cost at most $m+c(v_{i})$.

The generated out-subtrees cover all the nodes in $I_{i}$. We add $I_{s+1}$ to
the set of generated out-subtrees, if it exists. Let $T^{1},\ldots,T^{N}$ be
the set of generated out-subtrees. Since $I_{1},\dots,I_{s+1}$ cover all the
nodes of $\hat{T}$, then so do $T^{1},\ldots,T^{N}$. Moreover, each generated
out-subtree $T^{j}$ costs at most $m+c(r_{j})$, where $r_{j}$ is the root of
$T^{j}$.

We now bound the number $N$ of generated out-subtrees.

Given an infeasible out-subtree $I_{i}$, for some $i\in[s]$, each out-subtree
generated out of $I_{i}$ costs at least $m/2$, except for the possible out-
subtree made of only the root node of $I_{i}$ and a possible out-subtree of
cost smaller than $m/2$. Note that by construction at most one of these two
additional out-subtrees can be generated. Therefore, for each $i\in[s]$, the
number $s_{i}$ of out-subtrees generated out of $I_{i}$ is

$s_{i}\leq\left\lfloor\frac{c(I_{i})}{m/2}\right\rfloor+1\leq
2\left\lfloor\frac{c(I_{i})}{m}\right\rfloor+2\leq
4\left\lfloor\frac{c(I_{i})}{m}\right\rfloor.$

Since $I_{1},\dots,I_{s+1}$ are disjoint, then the overall number of generated
out-subtrees is at most $N\leq 1+\sum_{i\in[s]}s_{i}\leq
1+\sum_{i\in[s]}4\left\lfloor\frac{c(I_{i})}{m}\right\rfloor\leq
5\left\lfloor\frac{c(\hat{T})}{m}\right\rfloor$. ∎

Now we are ready to prove Theorem 3.1.

###### Proof of Theorem 3.1.

By applying Lemma 4.3 to an optimal solution $T^{*}$ and by setting
$m=\lfloor\sqrt{B}\rfloor$, we obtain $N\leq 5\lfloor\sqrt{B}\rfloor$ out-
subtrees $T^{i}=(V^{i},A^{i})$ of $T^{*}$, for $i\in[N]$, where
$V^{i}\subseteq V(T^{*})$, $A^{i}=(V^{i}\times V^{i})\cap A(T^{*})$,
$c(V^{i})\leq c(r_{i})+\lfloor\sqrt{B}\rfloor$, $r_{i}$ is the root of
$T^{i}$, and $\bigcup_{i=1}^{N}V^{i}=T^{*}$. Let
$p(T^{\prime})=\max\\{p(T^{i}):i\in[N]\\}$ and $w$ be the root of
$T^{\prime}$. The submodularity of $p$ implies
$p(T^{*})=p\left(\bigcup_{i=1}^{N}V(T^{i})\right)\leq Np(T^{\prime}),$ which
implies

$\displaystyle\\!\\!\\!\\!\\!\\!\\!\\!p(T)\geq p(T_{z})\geq
p(S_{w})\geq(1-e^{-1})p(S^{*}_{w})\geq(1-e^{-1})p(T^{\prime})\geq\frac{1-e^{-1}}{N}p(T^{*})\geq\frac{1-e^{-1}}{5\lfloor\sqrt{B}\rfloor}p(T^{*}),$
(3)

where the first two inequalities hold by the definitions of $z$ and $S_{w}$
and by the monotonicity of function $p$; The Third inequality holds because
$S_{w}$ is a $(1-e^{-1})$-approximate solution for instance $I^{RSM}_{w}$; The
fourth inequality holds as (i) $T^{\prime}$ contains nodes at a distance no
more than $c(w)+\lfloor\sqrt{B}\rfloor$ from $w$ and contains at most
$1+\lfloor\sqrt{B}\rfloor$ nodes (since the minimum cost of a node is at least
1) and (ii) $p(S^{*}_{w})=\max\\{p(S):|S|\leq 1+\lfloor\sqrt{B}\rfloor\text{
and }dist(w,v)\leq c(w)+\lfloor\sqrt{B}\rfloor\text{, for all }v\in S\\}$.

Before the trimming process in Lemma 4.2, the ratio between the prize and the
cost of $T$ is at least $\gamma=\frac{1-e^{-1}}{10\sqrt{B}B}p(T^{*})$ as
$c(T)\leq 2B$. After applying the trimming process in Lemma 4.2 (with $h=2$)
to $T$, the cost of $T$ is at most $(1+\varepsilon)B$ and its prize-to-cost
ratio is:

$\frac{p(T)}{c(T)}\geq\frac{\varepsilon^{2}\gamma}{64}=\alpha\frac{\varepsilon^{2}}{\sqrt{B}B}p(T^{*}),$

where $\alpha=\frac{1-e^{-1}}{640}$. As $c(T)\geq\varepsilon B/2$, we have
$p(T)\geq\frac{\alpha\varepsilon^{3}}{2\sqrt{B}}p(T^{*})$, which concludes the
proof. ∎

##  5 The unrooted version of DRSO

Here we consider the unrooted version of DRSO, denoted by DSO, in which the
goal is to find an out-tree $T$ of $D$ such that $c(T)\leq B$ and $p(T)$ is
maximum. Note that $T$ can be rooted at any vertex. By guessing the root of an
optimal solution, we can apply the algorithm in the previous section to obtain
a bicriteria $(1+\varepsilon,O(\frac{\sqrt{B}}{\varepsilon^{3}}))$
approximation. We now show that DSO admits an $O(\sqrt{B})$-approximation
algorithm with no budget violations. To do this, we first provide an unrooted
version of Lemma 4.2 in which it is not necessary to violate the budget
constraint at all when each vertex costs at most half of the budget. This
trimming process follows the same process as that of Lemma 4.2, but the proof
is included for the sake of completeness.

######  Lemma 5.1.

Let $T$ be an out-tree with the prize-to-cost ratio
$\gamma=\frac{p(T)}{c(T)}$, where $p$ is a monotone submodular function.
Suppose $\frac{B}{2}\leq c(T)\leq hB$, where $h>1$ and the cost of each vertex
is at most $\frac{B}{2}$. One can find an out-subtree $\hat{T}\subseteq T$
with the prize-to-cost ratio at least $\frac{\gamma}{32h+8}$ such that
$B/4\leq c(\hat{T})\leq B$.

###### Proof.

In the initial step, we remove a strict out-subtree $T^{\prime}$ of $T$ if (i)
the prize-to-cost ratio of $T\setminus T^{\prime}$ is at least $\gamma$, and
(ii) $c(T\setminus T^{\prime})\geq\frac{B}{4}$. This process is performed
iteratively, until no such out-subtree exists. Let $T_{-}$ be the remaining
out-subtree after applying this iterative process on $T$.

If $c(T_{-})\leq B$, the desired out-subtree is obtained and we are done.
Suppose it is not the case. A full out-subtree $T^{\prime}$ is called _rich_
if $c(T^{\prime})\geq\frac{B}{4}$ and the prize-to-cost ratio of $T^{\prime}$
and all its strict out-subtrees are at least $\gamma$. As in Lemma 4.2, we
claim that the lemma follows from the existence of a rich out-subtree.

######  Claim 5.1.

Given a rich out-subtree $T^{\prime}$, the desired out-subtree $\hat{T}$ can
be found.

###### Proof.

Let $T^{\prime\prime}$ be the lowest rich out-subtree of $T^{\prime}$ such
that the strict out-subtrees of $T^{\prime\prime}$ are not rich, i.e.,
$c(T^{\prime\prime})\geq\frac{B}{4}$ while the cost of strict out-subtrees of
$T^{\prime\prime}$ (if any exist) is less than $\frac{B}{4}$. Let $C$ be the
total cost of the immediate out-subtrees of $T^{\prime\prime}$. We distinguish
between two cases:

  1. 1.

If $C<\frac{B}{4}$, then $c(T^{\prime\prime})\leq\frac{3B}{4}$ as the root of
$T^{\prime\prime}$ costs at most $\frac{B}{2}$. Since $T^{\prime\prime}$ has
the prize-to-cost ratio at least $\gamma$ and cost at least $\frac{B}{4}$ (as
it is rich), $\hat{T}=T^{\prime\prime}$ is the desired out-subtree.

  2. 2.

If $C\geq\frac{B}{4}$, we first group the immediate out-subtrees of
$T^{\prime\prime}$ into $M$ groups $S_{1},\dots,S_{M}$, where each groups
costs at least $\frac{B}{4}$ and at most $\frac{B}{2}$. As $c(T_{-})\leq hB$,
we have

$M\leq\left\lceil\frac{hB}{B/4}\right\rceil=\left\lceil 4h\right\rceil\leq
4h+1.$

For each $i\in[M]$, let $S^{\prime}_{i}=S_{i}\cup\\{r^{\prime\prime}\\}$,
where $r^{\prime\prime}$ is the root of $T^{\prime\prime}$. Let
$z=\arg\max_{i\in[M]}p(S^{\prime}_{i})$. Hence by the submodularity and
monotonicity of $p$, we have

$p(S^{\prime}_{z})\geq\frac{\sum_{i=1}^{M}p(S^{\prime}_{i})}{4h+1}\geq\frac{p(S^{\prime}_{1})+\sum_{i=2}^{M}p(S_{i})}{4h+1}\geq\frac{p(S^{\prime}_{1}\cup\bigcup_{i=2}^{M}S_{i})}{4h+1}=\frac{p(T^{\prime\prime})}{4h+1}\geq\frac{\gamma}{16h+4}B,$

where the last inequality holds as $p(T^{\prime\prime})\geq\gamma\frac{B}{4}$
(since $T^{\prime\prime}$ is reach). Let $\hat{T}$ be the union of
$r^{\prime\prime}$, the edges from $r^{\prime\prime}$ to the roots of the out-
subtrees in $S_{z}$, and $S_{z}$. The cost of $\hat{T}$ is at most $B$. Hence
the prize-to-cost ratio of $\hat{T}$ is at least
$\frac{\gamma}{16h+4}\geq\frac{\gamma}{32h+8}$.∎

It only remains to consider the case when there is no reach out-subtree. Since
$T_{-}$ is not reach and $c(T_{-})\geq\frac{B}{4}$, the ratio of at least one
of the strict out-subtrees of $T_{-}$ is less than $\gamma$. Now we find an
out-subtree $T^{\prime}$ with ratio less than $\gamma$ such that the ratio of
all of its strict out-subtrees (if any exist) is at least $\gamma$. Since the
ratio of $T^{\prime}$ is less than $\gamma$ and $T^{\prime}$ is not removed in
the initial process, $c(T_{-}\setminus T^{\prime})<\frac{B}{4}$ (this can be
shown by the same argument as that of Claim 4.2). As $c(T_{-})>B$ and the cost
of the root of $T^{\prime}$ is at most $\frac{B}{2}$, the total cost of the
immediate out-subtrees of $T^{\prime}$ is at least $\frac{B}{4}$. Also, the
cost of an immediate out-subtree of $T^{\prime}$ is less than $\frac{B}{4}$,
otherwise we have a rich out-subtree. As the ratio and cost of $T_{-}$ are at
least $\gamma$ and $\frac{B}{4}$, respectively, then
$p(T_{-})\geq\frac{\gamma}{4}B$. We distinguish between two cases.

  1. 1.

If $p(T^{\prime})\geq\frac{\gamma}{8}B$, by the similar reasoning as above, we
partition the immediate out-subtrees of $T^{\prime}$ to $M$ groups
$S_{1},\dots,S_{M}$ where each group costs at least $\frac{B}{4}$ and at most
$\frac{B}{2}$. For each $i\in[M]$, let
$S^{\prime}_{i}=S_{i}\cup\\{r^{\prime}\\}$ where $r^{\prime}$ is the root of
$T^{\prime}$. Let $z=\arg\max_{i\in[M]}p(S^{\prime}_{i})$. As $M\leq 4h+1$, by
the submodularity and monotonicity of $p$ we have:

$p(S^{\prime}_{z})\geq\frac{\sum_{i=1}^{M}p(S^{\prime}_{i})}{4h+1}\geq\frac{p(S^{\prime}_{1})+\sum_{i=2}^{M}p(S_{i})}{4h+1}\geq\frac{p(S^{\prime}_{1}\cup\bigcup_{i=2}^{M}S_{i})}{4h+1}=\frac{p(T^{\prime})}{4h+1}\geq\frac{\gamma}{32h+8}B,$

where the last inequality holds as $p(T^{\prime})\geq\frac{\gamma}{8}B$. Let
$\hat{T}$ be the union of $r^{\prime}$, the edges from $r^{\prime}$ to the
roots of the out-subtrees in $S_{z}$ and $S_{z}$. The cost of $\hat{T}$ is at
most $B$ and its prize-to-cost ratio is at least $\frac{\gamma}{32h+8}$.

  2. 2.

If $p(T^{\prime})<\frac{\gamma}{8}B$, we proceed as follows. Consider the out-
subtree $T^{\prime\prime}=T_{-}\setminus T^{\prime}$. Recall that by the above
discussion we have $c(T^{\prime\prime})<\frac{B}{4}$. Thus we find a subset
$S$ of the immediate out-subtrees of $T^{\prime}$ with cost between
$\frac{B}{4}-c(T^{\prime\prime})\leq c(S)\leq\frac{B}{2}-c(T^{\prime\prime})$.
Note that such set $S$ can be found as each immediate out-subtree of
$T^{\prime}$ costs less than $\frac{B}{4}$ (otherwise we have a rich subtree)
and $c(T^{\prime\prime})>\frac{3B}{4}$ (as $c(T_{-})>B$ and
$c(T^{\prime\prime})<\frac{B}{4}$). Then let $\hat{T}$ be the union of
$T^{\prime\prime}$, the edge from $T^{\prime\prime}$ to $r^{\prime}$ in
$T_{-}$, $S$, and the edges from $r^{\prime}$ to the roots of the out-subtrees
in $S$, where $r^{\prime}$ is the root of $T^{\prime}$. We now bound the
prize-to-cost ratio of $\hat{T}$. Recall that $T^{\prime\prime}=T_{-}\setminus
T^{\prime}$. First note that by the submodularity’ properties
$p(T^{\prime\prime})+p(T^{\prime})\geq f(T_{-})$. Thus by the case assumption
and monotonicity, we have $f(\hat{T})\geq
p(T^{\prime\prime})\geq\frac{\gamma}{8}B$. Since
$\frac{B}{4}B-c(T^{\prime\prime})\leq c(S)\leq\frac{B}{2}-c(T^{\prime\prime})$
and $c(r^{\prime})\leq\frac{B}{2}$, $c(\hat{T})\leq B$. Therefore, the prize-
to-cost ratio of $\hat{T}$ is at least
$\frac{\gamma}{8}\geq\frac{\gamma}{32h+8}$.

The proof is complete. ∎

######  Theorem 5.1.

DSO admits a polynomial-time $O(\sqrt{B})$-approximation algorithm.

###### Proof.

We follow arguments similar to those in Theorem 4 from Bateni et al. [2], but
for the sake of completeness the proof is provided here.

An out-tree is called flat if each vertex of the out-tree costs no more than
$\frac{B}{2}$. Let $x$ be a vertex of an out-tree with the largest cost. An
out-tree is called saddled if $c(x)>\frac{B}{2}$ and the cost of every other
vertex of the out-tree is no more than $\frac{B-c(x)}{2}$. Let $T^{*}_{f}$
(resp. $T^{*}_{s}$) be the optimal flat (resp. saddled) out-tree, i.e, a flat
(resp. saddled) out-tree with cost at most $B$ maximizing the prize. We first
show that given an optimal solution $T^{*}$ to DSO, then either
$p(T^{*}_{f})\geq\frac{p(T^{*})}{2}$ or $p(T^{*}_{s})\geq\frac{p(T^{*})}{2}$.

######  Claim 5.2.

Either $p(T^{*}_{f})\geq\frac{p(T^{*})}{2}$ or
$p(T^{*}_{s})\geq\frac{p(T^{*})}{2}$, where $T^{*}$ is an optimal solution to
DSO.

###### Proof.

If $T^{*}$ has only one vertex, then it is either flat or saddled and we are
done. If $T^{*}$ has more than one vertex and it is neither flat nor saddled,
then we proceed as follows. Let $x$ and $y$ be two vertices in $T^{*}$ with
the maximum cost and the second maximum cost, respectively. Since $T^{*}$ is
not flat then $c(x)>\frac{B}{2}$ and $c(y)\leq\frac{B}{2}$. Also as $T^{*}$ is
not saddled, $c(y)>\frac{B-c(x)}{2}$, and, since the cost of $T^{*}$ is at
most $B$, $y$ is the only node with a cost higher than $\frac{B-c(x)}{2}$. By
removing the edge $e$ adjacent to $y$ on the path between $x$ and $y$, we can
partition $T^{*}$ into two out-subtrees $T^{*}_{x}$ and $T^{*}_{y}$ that
contain $x$ and $y$, respectively. Clearly, each vertex in $T^{*}_{y}$ costs
no more than $\frac{B}{2}$, then $T^{*}_{y}$ is flat. Also, each vertex in
$T^{*}_{x}$ except $x$ costs at most $\frac{B-c(x)}{2}$, implying that
$T^{*}_{x}$ is saddled. By the submodularity of $p$,
$p(T^{*}_{x})+p(T^{*}_{y})\geq p(T^{*})$, meaning that one of $T^{*}_{x}$ and
$T^{*}_{y}$ has at least half of the optimum prize $p(T^{*})$, which concludes
the claim. ∎

Now we restrict Algorithm 1 to only flat and saddled out-trees. Indeed, we can
reduce the case of saddled out-trees to flat out-trees as follows. We first
find a vertex $x$ with the maximum cost. We then set the cost of $x$ to zero
and define a new budget $B=B-c(x)$. Note that the cost of any other vertex in
the optimal saddled out-tree $T^{*}_{s}$ is at most half of the remaining
budget. This means that we only need to find an approximation solution when
restricted to flat out-trees.

Since for the new instance no other vertex except $x$ with cost more than
$\frac{B}{2}$ can be contained in the final solution, we remove all vertices
with cost more than $\frac{B}{2}$ and run Lines 1-8 of Algorithm 1 on the new
resulting graph to achieve an out-tree $T$ with cost $c(T)\leq 2B$ (as
$c(T\setminus\\{z\\})=B$ and $c(z)\leq B$) and prize
$p(T)\geq\frac{1-e^{-1}}{5\sqrt{B}}p(T^{*}_{f})\geq\frac{1-e^{-1}}{10\sqrt{B}}p(T^{*})$.
So, the prize-to-cost ratio of $T$ is $\gamma\geq\frac{p(T)}{2B}$. As $T$ is
flat, we can apply Lemma 5.1 to achieve an out-subtree $\hat{T}$ of $T$ with
the cost $B/4\leq c(\hat{T})\leq B$ and the prize-to-cost ratio
$\frac{p(\hat{T})}{c(\hat{T})}\geq\frac{\gamma}{32h+8}=\frac{\gamma}{72}$ as
$h\leq 2$. This implies that

$p(\hat{T})\geq\frac{\gamma}{72}\cdot\frac{B}{4}=\frac{\gamma}{288}B\geq\frac{p(T)}{576}\geq\frac{1-e^{-1}}{5760\sqrt{B}}p(T^{*}).\qed$

##  6 Submodular Tree Orienteering

Recently, Ghuge and Nagarajan [10] studied the _Submodular Tree Orienteering_
problem (STO), which is similar to DRSO with the only difference that the
costs are associated to the edges of a directed graph instead of the nodes. In
particular, in STO, we are given a directed graph $D=(V,A)$, a vertex $r\in
V$, a budget $B$, a monotone submodular function
$p:2^{V}\rightarrow\mathbb{R}^{+}$, and a cost $c:A\rightarrow\mathbb{Z}^{+}$,
and the goal is to find an out-subtree $T$ of $D$ rooted at $r$ such that
$\sum_{e\in A(T)}c(v)\leq B$ and $p(T)=p(V(T))$ is maximum. Ghuge and
Nagarajan [10] proposed an $O\left(\frac{\log k}{\log\log
k}\right)$-approximation algorithm for STO that runs in $(n\log
B)^{O(\log^{1+\varepsilon}k)}$ time for any constant $\varepsilon>0$, where
$k\leq|V|$ is the number of vertices in an optimal solution.

Here we first show that DRSO can be reduced to STO, preserving the
approximation factor, by assigning the cost of each node $v$ to all edges
entering $v$.

######  Theorem 6.1.

There is an $O(\frac{\log k}{\log\log k})$-approximation algorithm for DRSO
that runs in $(n\log B)^{O(\log^{1+\varepsilon}k)}$ time for any constant
$\varepsilon>0$, where $k\leq n=|V|$ is the number of vertices in an optimal
solution.

###### Proof.

To prove the theorem, we show that one can transform an instance $J=\langle
D^{\prime}=(V^{\prime},A^{\prime}),p^{\prime},c^{\prime},r^{\prime},B^{\prime}\rangle$
of DRSO to an instance $I=\langle D=(V,A),p,c,r,B\rangle$ of STO as follows.
We set $V=V^{\prime}$, $r=r^{\prime}$,
$A=A^{\prime}\setminus\\{(v,r^{\prime})|(v,r^{\prime})\in A^{\prime}\\}$,
$B=B^{\prime}-c^{\prime}(r^{\prime})$ and for any subset $S\subseteq V$,
$p(S)=p^{\prime}(S)$. For any $e=(i,j)\in A$ in $I$, we set
$c(e)=c^{\prime}(j)$. The theorem follows by observing that any out-subtree
$T$ of $D$ is an out-subtree for $D^{\prime}$, $c^{\prime}(T)=\sum_{v\in
V(T)}c^{\prime}(v)=\sum_{e=(u,v)\in
A(T)}c(e)+c^{\prime}(r^{\prime})=c(T)+c^{\prime}(r^{\prime})$, and
$p^{\prime}(T)=p(T)$. ∎

More importantly, we show that Algorithm 1 can be used to approximate STO. To
our knowledge, this is the first polynomial-time bicriteria approximation
algorithm for STO.

######  Theorem 6.2.

There exists a polynomial-time bicriteria
$(1+\varepsilon,O(\frac{\sqrt{B}}{\varepsilon^{3}}))$-approximation algorithm
for STO, for any $\varepsilon\in(0,1]$.

###### Proof.

We first transform an instance $I_{S}=\langle
D_{S}=(V_{S},A_{S}),p_{S},c_{S},r,B\rangle$ of STO to an instance
$I_{D}=\langle D_{D}=(V_{D},A_{D}),p_{D},c_{D},r,B\rangle$ of DRSO, where
$V_{D}=V_{S}\cup V_{A}$, $V_{A}=\\{v_{e}:e\in A_{S}\\}$,
$A_{D}=\\{(i,v_{e}),(v_{e},j):e=(i,j)\in A_{S}\\}$, $p_{D}(S)=p_{S}(S\cap
V_{S})$, for each $S\subseteq V_{D}$, $c_{D}(v)=0$ for each $v\in V_{S}$, and
$c_{D}(v_{e})=c_{S}(e)$ for each $v_{e}\in V_{A}$.

Let $T^{*}_{S}$ be an optimal solution for $I_{S}$ and let $T^{*}_{D}$ be the
out-subtree of $D^{\prime}$ corresponding to $T^{*}_{S}$ (i.e.
$V(T^{*}_{D})=V(T^{*}_{S})\cup\\{v_{e}:e\in A(T^{*}_{S})\\}$,
$A(T^{*}_{D})=\\{(i,v_{e}),(v_{e},j):e=(i,j)\in A(T^{*}_{S})\\}$). We observe
that $p_{D}(T^{*}_{D})=p_{S}(T^{*}_{S})$, $c_{D}(T^{*}_{D})=c_{S}(T^{*}_{S})$,
and $T^{*}_{D}$ is an optimal solution for $I_{D}$, since if there exists an
out-subtree $\bar{T}_{D}$ of $D_{D}$ with
$p_{D}(\bar{T}_{D})>p_{D}(T^{*}_{D})$, then we can construct an out-subtree
$\bar{T}_{S}=(V(\bar{T}_{D})\cap V_{S},\\{e\in A_{S}:v_{e}\in
V(\bar{T}_{D})\cap V_{A}\\})$ of $D_{S}$ such that
$p_{S}(\bar{T}_{S})>p_{S}(T^{*}_{S})$.

We decompose $T^{*}_{D}$ as in Lemma 4.3,222Note that the Lemma 4.2 and 4.3
hold even if node costs are allowed to be equal to 0. with
$m=\lfloor\sqrt{B}\rfloor$; let $T^{\prime}_{D}$ be the out-subtree that
maximizes the prize among those returned by the lemma, and let $w$ be the root
of $T^{\prime}_{D}$. We have that
$p_{D}(T^{\prime}_{D})\geq\frac{1}{5\lfloor\sqrt{B}\rfloor}p_{D}(T^{*}_{D})$
and $c(T^{\prime}_{D})\leq c(w)+\lfloor\sqrt{B}\rfloor$. It follows that the
distance from $w$ to any other node in $T^{\prime}_{D}$ is at most
$c(w)+\lfloor\sqrt{B}\rfloor$.

We now show that $|V(T^{\prime}_{D})\cap V_{S}|\leq\lfloor\sqrt{B}\rfloor+1$.
Since the cost of nodes in $V_{S}$ is equal to 0, then
$c((V(T^{\prime}_{D})\cap
V_{A})\setminus\\{w\\})=c(V(T^{\prime}_{D})\setminus\\{w\\})\leq\lfloor\sqrt{B}\rfloor$.
Therefore, as the cost of each edge in $A_{S}$ is at least 1,
$|(V(T^{\prime}_{D})\cap V_{A})\setminus\\{w\\}|\leq\lfloor\sqrt{B}\rfloor$.
For every node in $(V(T^{\prime}_{D})\cap V_{S})\setminus\\{w\\}$ there exists
a distinct node in $V(T^{\prime}_{D})\cap V_{A}$, which means that
$|(V(T^{\prime}_{D})\cap V_{S})\setminus\\{w\\}|=|V(T^{\prime}_{D})\cap
V_{A}|$. If $w\in V_{S}$, then $|V(T^{\prime}_{D})\cap
V_{A}|=|(V(T^{\prime}_{D})\cap
V_{A})\setminus\\{w\\}|\leq\lfloor\sqrt{B}\rfloor$. If $w\in V_{A}$, then
$|(V(T^{\prime}_{D})\cap V_{A})|\leq\lfloor\sqrt{B}\rfloor+1$. In both cases
$|V(T^{\prime}_{D})\cap V_{S}|\leq\lfloor\sqrt{B}\rfloor+1$.

Let $T_{D}$ be the output of lines 1-11 of Algorithm 1 for instance $I_{D}$.
We have that

$\displaystyle
p_{D}(T_{D})\geq(1-e^{-1})p_{D}(S^{*}_{w})\geq(1-e^{-1})p_{D}(T^{\prime}_{D})\geq\frac{1-e^{-1}}{5\lfloor\sqrt{B}\rfloor}p_{D}(T^{*}_{D})=\frac{1-e^{-1}}{5\lfloor\sqrt{B}\rfloor}p_{S}(T^{*}_{S}),$

where the second inequality is due to the fact that (i) $T^{\prime}_{D}$
contains nodes at a distance no more than $c(w)+\lfloor\sqrt{B}\rfloor$ from
$w$ and contains at most $\lfloor\sqrt{B}\rfloor+1$ nodes in $V_{S}$, and (ii)
$p_{D}(S)=p_{D}(S\cap V_{S})$, for each $S\subseteq V_{D}$, and therefore
$p_{D}(S^{*}_{w})=\max\\{p_{D}(S):|S\cap
V_{S}|\leq\lfloor\sqrt{B}\rfloor+1\text{ and }dist(w,v)\leq
c(w)+\lfloor\sqrt{B}\rfloor\text{, for all }v\in S\\}$. The other inequalities
are analogous to those in (3).

The cost of $T_{D}$ is at most $2B$, as in Theorem 3.1 we can trim $T_{D}$ to
reduce its cost to $(1+\varepsilon)B$ and maintaining a prize of
$p_{D}(T_{D})=\frac{\alpha\varepsilon^{2}}{\sqrt{B}}p(T^{*}_{S})$, for some
constant $\alpha$ and any arbitrary $\varepsilon>0$.

Let us consider the out-subtree $T_{S}$ of $D_{S}$ corresponding to $T_{D}$,
$T_{S}=(V(T_{D})\cap V_{S},\\{e\in A_{S}:v_{e}\in V(T_{D})\cap V_{A}\\})$,
then $p_{S}(T_{S})=p_{D}(T_{D})$ and $c_{S}(T_{S})=c_{D}(T_{D})$, which
concludes the proof. ∎

##  7 Further Results on Some Variants of DRSO

In this section, we provide approximation results on some variants of DRSO.
All the details are given in Appendix B.

Additive prize function and Directed Tree Orienteering (DTO). We consider the
special case of DRSO in which the prize function is additive, i.e.,
$p:V\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ and for any $S\subseteq V$,
$p(S)=\sum_{v\in S}p(v)$, called DRAO. We show that there exists a polynomial-
time bicriteria $(1+\varepsilon,O(\sqrt{B}/\varepsilon^{2}))$-approximation
algorithm for DRAO (Theorem B.1). By using the reduction in Theorem 6.2, it
follows that this result also holds for DTO, which is the special case of STO
in which the prize function is additive [10].

Undirected graphs. All our results hold also in the case in which the input
graph is undirected and the output graph is a tree. In particular, our
$O(\sqrt{B})$-approximation algorithm for the unrooted case improves over the
factors $O((\Delta+1)\sqrt{B})$ [22] and $\min\\{1/((1-1/e)(1/R-1/B)),B\\}$
[14], where $R$ is the radius of the input graph $G$. For the case in which
the prize function is additive, we show that there exists a polynomial-time
bicriteria approximation algorithm whose approximation factor only depends on
the the maximum degree $\Delta$ of the given graph. In particular, it
guarantees a bicriteria
$(1+\varepsilon,16\Delta/\varepsilon^{2})$-approximation (Theorem B.2).

Quota problem. We consider the problem in which we are given an undirected
graph $G=(V,E)$, a cost function $c:V\rightarrow\mathbb{R}^{+}$, a prize
function $p:V\rightarrow\mathbb{R}^{+}$, a quota $Q\in\mathbb{R}^{+}$, and a
vertex $r$, and the goal is to find a tree $T$ such that $p(T)\geq Q$, $r\in
V(T)$ and $c(T)$ is minimum. We prove that this problem admits a
$2\Delta$-approximation algorithm (Theorem B.3).

Maximum Weighted Budgeted Connected Set Cover (MWBCSC). Let $X$ be a set of
elements, $\mathcal{S}\subseteq 2^{X}$ be a collection of sets,
$p:X\rightarrow\mathbb{R}^{+}$ be a prize function,
$c:\mathcal{S}\rightarrow\mathbb{R}^{+}$ be a cost function, $G_{\mathcal{S}}$
be a graph on vertex set $\mathcal{S}$, and $B$ be a budget. In MWBCSC, the
goal is to find a subcollection $\mathcal{S}^{\prime}\subseteq\mathcal{S}$
such that $c(\mathcal{S}^{\prime})=\sum_{S\in\mathcal{S}^{\prime}}c(S)\leq B$,
the subgraph induced by $\mathcal{S}^{\prime}$ is connected and
$p(\mathcal{S}^{\prime})=\sum_{x\in X_{\mathcal{S}^{\prime}}}p(x)$ is maximum,
where $X_{\mathcal{S}^{\prime}}=\bigcup_{S\in\mathcal{S}^{\prime}}S$. We show
that MWBCSC admits a polynomial-time $\alpha f$-approximation algorithm, where
$f$ is the maximum frequency of an element and $\alpha$ is the performance
ratio of an algorithm for the unrooted version of MCSB with additive prize
function (Theorem B.4). Moreover, one can have a polynomial-time
$O(\log{n})$-approximation algorithm for MWBCSC under the assumption that if
two sets have an element in common, then they are adjacent in
$G_{\mathcal{S}}$ (Corollary B.2). This last result is an improvement over the
factor $2(\Delta+1)\alpha/(1-e^{-1})$ by Ran et al. [29].

Budgeted Sensor Cover Problem (BSCP). In BSCP, we are given a set
$\mathcal{S}$ of sensors, a set $\mathcal{P}$ of target points in a metric
space, a sensing range $R_{s}$, a communication range $R_{c}$, and a budget
$B$. A target point is covered by a sensor if it is within distance $R_{s}$
from it. Two sensors are connected if they are at a distance at most $R_{c}$.
The goal is to find a subset $\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such
that $|\mathcal{S}^{\prime}|\leq B$, the number of covered target points by
$\mathcal{S}^{\prime}$ is maximized and $\mathcal{S}^{\prime}$ induces a
connected subgraph. We give a $2f$-approximation algorithm for BSCP (Theorem
B.5), where $f$ is the maximum number of sensors that cover a target point. We
also show that, under the assumption that $R_{s}\leq R_{c}/2$, BSCP admits a
polynomial-time $8/(1-e^{-1})$-approximation algorithm (Theorem B.8), which
improves the factors $8(\lceil 2\sqrt{2}C\rceil+1)^{2}/(1-1/e)$ [16] and
$8(\lceil 4C/\sqrt{3}\rceil+1)^{2}/(1-1/e)$ [33], where $C=R_{s}/R_{c}$. Note
that Huang et al. [16] do not assume that $R_{s}/R_{c}\leq R_{c}/2$, however,
our technique improves over their result if $R_{s}\leq R_{c}/2$.

## References

  * [1] Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Howard J. Karloff.  Improved approximation algorithms for prize-collecting steiner tree and TSP.  SIAM J. Comput., 40(2):309–332, 2011.
  * [2] Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Vahid Liaghat.  Improved approximation algorithms for (budgeted) node-weighted steiner problems.  SIAM J. Comput., 47(4):1275–1293, 2018.
  * [3] Moses Charikar, Chandra Chekuri, To-Yat Cheung, Zuo Dai, Ashish Goel, Sudipto Guha, and Ming Li.  Approximation algorithms for directed steiner problems.  J. Algorithms, 33(1):73–91, 1999.
  * [4] Xuefeng Chen, Xin Cao, Yifeng Zeng, Yixiang Fang, and Bin Yao.  Optimal region search with submodular maximization.  In Christian Bessiere, editor, Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI, pages 1216–1222, 2020.
  * [5] Xiuzhen Cheng, Yingshu Li, Ding-Zhu Du, and Hung Q Ngo.  Steiner trees in industry.  In Handbook of combinatorial optimization, pages 193–216. Springer, 2004.
  * [6] Kiril Danilchenko, Michael Segal, and Zeev Nutov.  Covering users by a connected swarm efficiently.  In Algorithms for Sensor Systems - 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2020, , Revised Selected Papers, volume 12503 of Lecture Notes in Computer Science, pages 32–44. Springer, 2020.
  * [7] Xiaofeng Gao, Junwei Lu, Haotian Wang, Fan Wu, and Guihai Chen.  Algorithm design and analysis for wireless relay network deployment problem.  IEEE Trans. Mob. Comput., 18(10):2257–2269, 2019.
  * [8] N Garg.  A 3 factor approximation algorithm for the minimum tree spanning k vertices.  In Proc of 37th Symp. on Foundations of Computer Science, pages 302–309, 1996.
  * [9] Naveen Garg.  Saving an epsilon: a 2-approximation for the k-mst problem in graphs.  In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, pages 396–402. ACM, 2005\.
  * [10] Rohan Ghuge and Viswanath Nagarajan.  Quasi-polynomial algorithms for submodular tree orienteering and other directed network design problems.  In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1039–1048. SIAM, 2020.
  * [11] Michel X. Goemans and David P. Williamson.  A general approximation technique for constrained forest problems.  SIAM J. Comput., 24(2):296–317, 1995.
  * [12] Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li.  O(log${}^{\mbox{2}}$k/log log k)-approximation algorithm for directed steiner tree: A tight quasi-polynomial-time algorithm.  CoRR, abs/1811.03020, 2018.
  * [13] Sudipto Guha, Anna Moss, Joseph Naor, and Baruch Schieber.  Efficient recovery from power outage (extended abstract).  In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, pages 574–582. ACM, 1999.
  * [14] Dorit S. Hochbaum and Xu Rao.  Approximation algorithms for connected maximum coverage problem for the discovery of mutated driver pathways in cancer.  Inf. Process. Lett., 158:105940, 2020.
  * [15] Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Joseph S. B. Mitchell, and Nabil H. Mustafa.  Maximizing covered area in the euclidean plane with connectivity constraint.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2019, volume 145 of LIPIcs, pages 32:1–32:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019\.
  * [16] Lingxiao Huang, Jian Li, and Qicai Shi.  Approximation algorithms for the connected sensor cover problem.  Theor. Comput. Sci., 809:563–574, 2020.
  * [17] David S. Johnson, Maria Minkoff, and Steven Phillips.  The prize collecting steiner tree problem: theory and practice.  In David B. Shmoys, editor, Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 760–769. ACM/SIAM, 2000\.
  * [18] Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar.  Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems.  SIAM J. Discret. Math., 34(1):251–270, 2020.
  * [19] Philip N. Klein and R. Ravi.  A nearly best-possible approximation algorithm for node-weighted steiner trees.  J. Algorithms, 19(1):104–115, 1995.
  * [20] Jochen Könemann, Sina Sadeghian Sadeghabad, and Laura Sanità.  An LMP o(log n)-approximation algorithm for node weighted prize collecting steiner tree.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA, pages 568–577. IEEE Computer Society, 2013.
  * [21] Guy Kortsarz and Zeev Nutov.  Approximating some network design problems with node costs.  Theor. Comput. Sci., 412(35):4482–4492, 2011.
  * [22] Tung-Wei Kuo, Kate Ching-Ju Lin, and Ming-Jer Tsai.  Maximizing submodular set function with connectivity constraint: Theory and application to networks.  IEEE/ACM Trans. Netw., 23(2):533–546, 2015.
  * [23] Ioannis Lamprou, Ioannis Sigalas, and Vassilis Zissimopoulos.  Improved budgeted connected domination and budgeted edge-vertex domination.  Theor. Comput. Sci., 858:1–12, 2021.
  * [24] Heungsoon Felix Lee and Daniel R Dooly.  Algorithms for the constrained maximum-weight connected graph problem.  Naval Research Logistics (NRL), 43(7):985–1008, 1996.
  * [25] Shi Li and Bundit Laekhanukit.  Polynomial integrality gap of flow LP for directed steiner tree.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, pages 3230–3236. SIAM, 2022.
  * [26] Anna Moss and Yuval Rabani.  Approximation algorithms for constrained node weighted steiner tree problems.  SIAM J. Comput., 37(2):460–481, 2007.
  * [27] George L. Nemhauser, Laurence A. Wolsey, and Marshall L. Fisher.  An analysis of approximations for maximizing submodular set functions \- I.  Math. Program., 14(1):265–294, 1978.
  * [28] Alice Paul, Daniel Freund, Aaron M. Ferber, David B. Shmoys, and David P. Williamson.  Budgeted prize-collecting traveling salesman and minimum spanning tree problems.  Math. Oper. Res., 45(2):576–590, 2020.
  * [29] Yingli Ran, Zhao Zhang, Ker-I Ko, and Jun Liang.  An approximation algorithm for maximum weight budgeted connected set cover.  J. Comb. Optim., 31(4):1505–1517, 2016.
  * [30] Stephan Seufert, Srikanta J. Bedathur, Julián Mestre, and Gerhard Weikum.  Bonsai: Growing interesting small trees.  In Geoffrey I. Webb, Bing Liu, Chengqi Zhang, Dimitrios Gunopulos, and Xindong Wu, editors, ICDM 2010, The 10th IEEE International Conference on Data Mining, pages 1013–1018. IEEE Computer Society, 2010.
  * [31] Fabio Vandin, Eli Upfal, and Benjamin J. Raphael.  Algorithms for detecting significantly mutated pathways in cancer.  J. Comput. Biol., 18(3):507–522, 2011.
  * [32] Wenzheng Xu, Yueying Sun, Rui Zou, Weifa Liang, Qiufen Xia, Feng Shan, Tian Wang, Xiaohua Jia, and Zheng Li.  Throughput maximization of UAV networks.  IEEE/ACM Transactions on Networking, 30(2):881–895, 2022.
  * [33] Nan Yu, Haipeng Dai, Guihai Chen, Alex X. Liu, Bingchuan Tian, and Tian He.  Connectivity-constrained placement of wireless chargers.  IEEE Trans. Mob. Comput., 20(3):909–927, 2021.
  * [34] Alexander Zelikovsky.  A series of approximation algorithms for the acyclic directed steiner tree problem.  Algorithmica, 18(1):99–110, 1997.
  * [35] Chenyang Zhou, Anisha Mazumder, Arun Das, Kaustav Basu, Navid Matin-Moghaddam, Saharnaz Mehrani, and Arunabha Sen.  Relay node placement under budget constraint.  In Paolo Bellavista and Vijay K. Garg, editors, Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN, pages 35:1–35:11. ACM, 2018.

## Appendix

##  Appendix A Further Related Work

Zelikovsky [34] provided the first approximation algorithm for Directed
Steiner Tree Problem (DSTP) with factor
$O(k^{\varepsilon}(\log^{1/\varepsilon}{k}))$ that runs in
$O(n^{1/\varepsilon})$, where $|U|=k$. Charikar et al. [3] proposed a better
approximation algorithm for DSTP with a factor $O(\log^{3}{k})$ in quasi-
polynomial time. Grandoni et al. [12] improved this factor and provided a
randomized $O(\frac{\log^{2}k}{\log\log k})$-approximation algorithm
$n^{O(\log^{5}k)}$ time. Also, they showed that, unless
$NP\subseteq\bigcap_{0<\varepsilon<1}\text{ZPTIME}(2^{n^{\varepsilon}})$ or
the Projection Game Conjecture is false, there is no quasi-polynomial time
algorithm for DSTP that achieves an approximation ratio of
$o(\frac{\log^{2}k}{\log\log k})$. Ghuge and Nagarajan [10] showed that their
approximation algorithm results in a deterministic
$O(\frac{\log^{2}k}{\log\log k})$-approximation algorithm for DSTP in
$n^{O(\log^{1+\varepsilon}k)}$ time. Very recently, Li and Laekhanukit [25]
showed that the lower bound on the integrality gap of the flow LP is
polynomial in the number of vertices.

Danilchenko et al. [6] investigated a closely related problem to BSCP and
provided a polynomial-time $O(1)$-approximation algorithm. MCSB is also
closely related to budgeted connected dominating set problem, where the goal
is to select at most $B$ connected vertices in a given undirected graph to
maximize the profit function on the set of selected vertices. Khuller et al.
[18] investigated this problem in which the profit function is a _special
submodular function_. Khuller et al. [18] designed a
$\frac{12}{1-1/e}$-approximation algorithm. By generalizing the analysis of
Khuller et al. [18], Lamprou et al. [23] showed that there is a
$\frac{11}{1-e^{-7/8}}$-approximation algorithm for the budgeted connected
dominating set problem. They also showed that for this problem we cannot
achieve in polynomila time an approximation factor better than
$\left(\frac{1}{1-1/e}\right)$, unless $P=NP$.

Lee and Dooly [24] provided a $(B-2)$-approximation algorithm for URAT, where
each vertex costs $1$. Zhou et al. [35] studied a variant of E-URAT in the
wireless sensor networks and provided a $10$-approximation algorithm. Seufert
et al. [30] investigated a special case of the unrooted version of URAT, where
each vertex has cost $1$ and we aim to find a tree with at most $B$ nodes
maximizing the accumulated prize. This coincides with the unrooted version of
E-URAT when the cost of each edge is $1$ and we are looking for a tree
containing at most $B-1$ edges to maximize the accumulated prize. Seufert et
al. [30] provided a $(5+\varepsilon)$-approximation algorithm for this
problem. Similarly, Huang et al. [15] investigated this variant of E-URAT (or
URAT) in plane and proposed a $2$-approximation algorithm.

The quota variant of URAT also has been studied, which is called Q-URAT. Here
we wish to find a tree including a vertex $r$ in a way that the total cost of
the tree is minimized and its prize is no less than some _quota_. By using
Moss and Rabbani [26]’black box and the ideas of Könemann et al. [20], and
Bateni et al. [2], we have an $O(\log{n})$-approximation algorithm for Q-URAT.
This bound is tight [26]. The edge cost variant of Q-URAT, called EQ-URAT, has
been investigated by Johnson et al. [17]. They showed that by adapting an
$\alpha$-approximation algorithm for the $k$-MST problem, one can have an
$\alpha$-approximation algorithm for EQ-URAT. Hence, the $2$-approximation
algorithm of Garg [9] for the $k$-MST problem results in a $2$-approximation
algorithm for EQ-URAT.

The prize collecting variants of URAT have also been studied. Könemann et al.
[20] provided a Lagrangian multiplier preserving $O(\ln{n})$-approximation
algorithm for NW-PCST, where the goal is to minimize the cost of the nodes in
the resulting tree plus the penalties of vertices not in the tree. Bateni et
al. [2] considered a more general case of NW-PCST and provided an
$O(\log{n})$-approximation algorithm. There exists no
$o(\ln{n})$-approximation algorithm for NW-PCST, unless
$NP\subseteq\text{DTIME}(n^{\text{Polylog}(n)})$ [19]. The edge cost variant
of NW-PCST has been investigated by Goemans and Williamson [11]. They provided
a $2$-approximation algorithm for EW-PCST. Later, Archer et al. [1] proposed a
$(2-\varepsilon)$-approximation algorithm for EW-PCST which was an improvement
upon the long standing bound of $2$.

Problem | Best Bound
---|---
STO |  $O(\frac{\log{n}}{\log{\log{n}}})$ [10] (tight)
DTO |  $O(\frac{\log{n}}{\log{\log{n}}})$ [10] (tight)
DSTP |  $O(\frac{\log^{2}{k}}{\log{\log{k}}})$ [10, 12] (tight)
NW-PCST |  $O(\log{n})$ [2, 20] (tight)
EW-PCST |  $2-\varepsilon$ [1]
URAT |  $(1+\varepsilon,O(\frac{\log{n}}{\varepsilon^{2}}))$ [2, 20, 26]
E-URAT |  $2$ [28]
Q-URAT |  $O(\log{n})$ [2, 20, 26] (tight)
EQ-URAT |  $2$ [9, 17]
Table 1: A summary of the best bounds on some variants of prize collecting
problems.

##  Appendix B Some Variants of DRSO

### Additive prize function

We consider a the special case of DRSO where the prize function $p$ is an
additive function, i.e., $p:V\rightarrow\mathbb{R}^{+}\cup\\{0\\}$ and for any
$S\subseteq V$, $p(S)=\sum_{v\in S}p(v)$, which we call _Directed Rooted
Additive Out-tree_ (DRAO).

We apply a variant of Algorithm 1 to DRAO where, in Line 12 of the algorithm,
we use a different trimming process to achieve a better approximation factor.
In particular, we show that we can use the by trimming process by Bateni et
al. [2] (Lemma 4.1) in directed graphs and achieve the same guarantee.

Let us first briefly explain the trimming process by Bateni et al. [2]. We are
given an undirected graph $G=(V,E)$, a distinguished vertex $r\in V$ and a
budget $B$, where each vertex $v\in V$ is assigned with a prize
$p^{\prime}(v)$ and a cost $c^{\prime}(v)$. Let $T$ be a tree, where
$V(T)\subseteq V$ and $E(T)\subseteq E$, let $c^{\prime}(T)=\sum_{v\in
V(T)}c^{\prime}(v)$, and let $p^{\prime}(T)=\sum_{v\in V(T)}p^{\prime}(v)$.
The trimming procedure by Bateni et al. takes as input an out-subtree $T$
rooted at a node $r$ of a $B$-proper graph $G$ and first (i) computes an out-
subtree $T^{\prime\prime}$ of $T$, not necessarily rooted $r$, such that
$\frac{\varepsilon B}{2}\leq c^{\prime}(T^{\prime\prime})\leq\varepsilon B$
and $p^{\prime}(T^{\prime\prime})\geq\frac{\varepsilon B}{2}\gamma$, where
$\gamma=\frac{p^{\prime}(T)}{c^{\prime}(T)}$. Then (ii) it connects node $r$
to the root of $T^{\prime\prime}$ with a minimum-cost path and obtains a tree
$T^{\prime}$ rooted at $r$. Since $G$ is $B$-proper, this path exists and has
length at most $B$, which implies that the cost of the resulting tree is
between $\frac{\varepsilon B}{2}$ and $(1+\varepsilon)B$, and its prize to
cost ratio is at least
$\frac{p^{\prime}(T^{\prime\prime})}{(1+\varepsilon)B}\geq\frac{\varepsilon\gamma}{4}$.
This leads to Lemma 4.1. For directed graph we prove a lemma equivalent to
Lemma 4.1.

######  Lemma B.1.

Let $D=(V,A)$ be a $B$-appropriate graph for a node $r$. Let $T$ be an out-
tree of $D$ rooted at $r$ with the prize-to-cost ratio
$\gamma=\frac{p(T)}{c(T)}$. Suppose that for $\varepsilon\in(0,1]$,
$c(T)\geq\frac{\varepsilon B}{2}$. One can find an out-tree $\hat{T}$ rooted
at $r$ with the prize-to-cost ratio at least $\frac{\varepsilon\gamma}{4}$
such that $\varepsilon B/2\leq c^{\prime}(T^{\prime})\leq(1+\varepsilon)B$.

###### Proof.

We first define an undirected tree by removing the directions from $T$ and
apply to it the step (i) of the trimming procedure by Bateni et al. with
$p^{\prime}(\cdot)=p(\cdot)$ and $c^{\prime}(\cdot)=c(\cdot)$ as prize and
cost functions, respectively. We obtain a subtree $T^{\prime\prime}$ such that
$\frac{\varepsilon B}{2}\leq c^{\prime}(T^{\prime\prime})\leq\varepsilon B$
and $p^{\prime}(T^{\prime\prime})\geq\frac{\varepsilon B}{2}\gamma$. We
reintroduce in $T^{\prime\prime}$ the same directions as in $T$ to obtain an
out-tree $T^{\prime\prime}_{out}$ corresponding to $T^{\prime\prime}$. Then,
we add a minimum cost path from $r$ to the root of $T^{\prime\prime}_{out}$.
Since $D$ is $B$-appropriate, this path exists and has length at most $B$. The
obtained out-tree $\hat{T}$ has the desired properties because
$p(T^{\prime\prime}_{out})=p^{\prime}(T^{\prime\prime})$ and
$c(T^{\prime\prime}_{out})=c^{\prime}(T^{\prime\prime})$ and therefore
$\frac{\varepsilon B}{2}\leq c(\hat{T})\leq(1+\varepsilon)B$ and
$\frac{p(\hat{T})}{c(\hat{T})}\geq\frac{p^{\prime}(T^{\prime\prime})}{(1+\varepsilon)B}\geq\frac{\varepsilon\gamma}{4}$.
∎

This results in the following theorem.

######  Theorem B.1.

There exists a polynomial-time bicriteria
$(1+\varepsilon,O(\frac{\sqrt{B}}{\varepsilon^{2}}))$-approximation algorithm
for DRAO.

###### Sketch of proof.

The theorem follows by the same arguments used in the proof of Theorem 3.1 and
by Lemma B.1. ∎

### Undirected graphs

Here we consider the particular case of DRSO in which the graph is undirected.
Since it is a special case of DRSO, all our results hold.

Kuo et al. [22] studied the unrooted version of DRSO in undirected graphs,
which they call _Maximum Connected Submodular function with Budget constraint_
(MCSB). In MCSB, we are given an undirected graph $G=(V,E)$, a monotone
submodular function $p:2^{V}\rightarrow\mathbb{R}^{+}$, a cost function
$c:V\rightarrow\mathbb{Z}^{+}$ and a budget $B$, and the goal is to find a
tree $T$ s.t. $c(T)=\sum_{v\in V(T)}c(v)\leq B$ and $p(T)$ is maximum.

Kuo et al. provided an $O((\Delta+1)\sqrt{B})$-approximation algorithm for the
undirected rooted version of DRSO, where $\Delta$ is the maximum degree.
Recently, Hochbaum and Rao [14] investigated MCSB in the case in which each
vertex costs $1$ for the detection of mutated driver pathways in cancer and
provided an approximation algorithm with factor
$\min\\{\frac{1}{(1-1/e)(1/R-1/B)},B\\}$, where $R$ is the radius of the input
graph $G$.

Our algorithm for the unrooted version of DRSO can be applied to undirected
graphs and improves the above results [22, 14] by providing an
$O(\sqrt{B})$-approximation.

### Additive prize function in undirected graphs

We consider the problem where we are given an undirected graph $G=(V,E)$, a
cost function $c:V\rightarrow\mathbb{R}^{+}$, a prize function
$p:V\rightarrow\mathbb{R}^{+}$, a budget $B$ and a vertex $r$, and the goal is
to find a tree $T=$ such that $c(T)=\sum_{v\in V(T)}c(v)\leq B$, $r\in V(T)$
and $p(T)=\sum_{v\in V(T)}p(v)$ is maximum. We call this problem _Undirected
Rooted Additive Tree_ (URAT) and we show that it admits a bicriteria
polynomial-time approximation algorithm, which depends on the maximum degree
in the graph.

######  Theorem B.2.

URAT admits a polynomial-time bicriteria
$(1+\varepsilon,\frac{16\Delta}{\varepsilon^{2}})$-approximation algorithm,
where $\Delta$ is the maximum degree in the given graph.

To prove Theorem B.2, we need the following observations. Let E-URAT be the
same problem as URAT except that the edges and not the nodes have costs. In
particular, in E-URAT, we are given an undirected graph $G=(V,E)$, a cost
function $c:E\rightarrow\mathbb{R}^{+}$, a prize function
$p:V\rightarrow\mathbb{R}^{+}$, a budget $B$ and a vertex $r$, and the goal is
to find a tree $T=(V(T),E(T))$ such that $c(T)=\sum_{e\in E(T)}c(e)\leq B$,
$r\in V(T)$ and $p(T)=\sum_{v\in V(T)}p(v)$ is maximum. Paul et al. [28] gave
a $2$-approximation algorithm for E-URAT.

######  Lemma B.2.

Let $\mathcal{A}$ be an $\alpha$-approximation algorithm for E-URAT. Using
$\mathcal{A}$, a bicriteria $(\Delta,\alpha)$-approximation can be obtained
for URAT, where $\Delta$ is the maximum degree of a node.

###### Proof.

Consider an instance $I=\langle G=(V,E),p,c,r,B\rangle$ of URAT. We create an
instance $I^{\prime}=\langle G,p,c^{\prime},r,B^{\prime}\rangle$ of E-URAT
where $B^{\prime}=\Delta B$ and, for any edge $e=\\{u,v\\}\in E^{\prime}$, we
set $c^{\prime}(e)=c(u)+c(v)$. Let $OPT_{I}$ and $OPT_{I^{\prime}}$ be optimal
solutions to $I$ and $I^{\prime}$, respectively.

First, observe that $p(OPT_{I^{\prime}})\geq p(OPT_{I})$ as $OPT_{I}$ is a
feasible solution for $I^{\prime}$. By running $\mathcal{A}$ on instance
$I^{\prime}$, we have a tree $T^{\prime}$ with the cost
$c(T^{\prime})=\sum_{e\in E(T^{\prime})}c(e)\leq B^{\prime}=\Delta B$ and the
prize $p^{\prime}(T^{\prime})\geq\alpha p(OPT_{I^{\prime}})\geq\alpha
p(OPT_{I})$. Therefore $T^{\prime}$ is a $(\Delta,\alpha)$-approximation for
$I$. ∎

Now we are ready to prove Theorem B.2.

###### Proof of Theorem B.2.

Consider an instance $I=\langle G=(V,E),p,c,r,B\rangle$ of URAT. From graph
$G$, we first create a maximal inclusion-wise $B$-appropriate graph
$G^{\prime}$ for $r$. Let $OPT$ be an optimal solution to $I$. By Lemma B.2
and the $2$-approximation algorithm for E-URAT proposed by Paul et al. [28],
we create a subtree $T^{\prime}$ of $G^{\prime}$ with prize
$p(T)\geq\frac{OPT}{2}$ and cost $c(T)\leq\Delta B$. Now by using Lemma 4.1,
we obtain a subtree $\hat{T}$ from $T$ with the cost at most
$c(\hat{T})\leq(1+\varepsilon)B$ and the prize-to-cost ratio:

$\frac{p(\hat{T})}{c(\hat{T})}\geq\frac{\varepsilon
p(T)}{4c(T)}\geq\frac{\varepsilon}{8\Delta B}OPT_{B}.$

As $c(\hat{T})\geq\varepsilon B/2$, we have
$p(\hat{T})\geq\frac{\varepsilon^{2}}{16\Delta}OPT_{B}$, which concludes the
proof. ∎

### Quota Problem

We consider the quota version of URAT, called Q-URAT, where we are given an
undirected graph $G=(V,E)$, a cost function $c:V\rightarrow\mathbb{R}^{+}$, a
prize function $p:V\rightarrow\mathbb{R}^{+}$, a quota $Q\in\mathbb{R}^{+}$,
and a vertex $r$, and the goal is to find a tree $T$ such that
$p(T)=\sum_{v\in V(T)}p(v)\geq Q$, $r\in V(T)$ and $c(T)=\sum_{v\in V(T)}c(v)$
is minimum.

We provide a new polynomial-time approximation algorithm for Q-URAT that
depends on the maximum degree of the given graph.

######  Theorem B.3.

Q-URAT admits a $2\Delta$-approximation algorithm, where $\Delta$ is the
maximum degree of a node in the given graph.

To prove Theorem B.3, we first prove the following lemma. Let EQ-URAT be the
same problem as Q-URAT except that the edges and not the nodes have costs. In
particular, in EQ-URAT, we are given an undirected graph $G=(V,E)$, a cost
function $c:E\rightarrow\mathbb{R}^{+}$, a prize function
$p:V\rightarrow\mathbb{R}^{+}$, a quota $Q$ and a vertex $r$, and the goal is
to find a tree $T$ such that $p(T)=\sum_{v\in V(T)}p(v)\geq Q$, $r\in V(T)$
and $c(T)=\sum_{e\in E(T)}c(v)$ is minimum.

######  Lemma B.3.

Let $\mathcal{A}$ be an $\alpha$-approximation algorithm for EQ-URAT. Using
$\mathcal{A}$, an $\alpha\Delta$-approximation can be obtained for Q-URAT.

###### Proof.

From an instance $I=\langle G=(V,E),p,c,r,Q\rangle$ of Q-URAT, we create an
instance $I^{\prime}=\langle G,p,c^{\prime},r,Q\rangle$ of EQ-URAT, where, for
any edge $e=\\{u,v\\}\in E^{\prime}$, we set $c^{\prime}(e)=c(u)+c(v)$.

By running $\mathcal{A}$ on instance $I^{\prime}$, we have a tree $T$ with
prize $p(T)\geq Q$ and cost $c^{\prime}(T)\leq\alpha
c^{\prime}(OPT_{I^{\prime}})$, where $OPT_{I^{\prime}}$ is an optimal solution
to $I^{\prime}$. Moreover, we have that $c(T)\leq c^{\prime}(T)$ and
$c^{\prime}(OPT_{I})\leq\Delta c(OPT_{I})$, where $OPT_{I}$ is an optimal
solution to $I$. We obtain $c(T)\leq\alpha\Delta c(OPT_{I})$. Therefore $T$ is
an $\alpha\Delta$-approximation for $I$. ∎

Now we prove Theorem B.3.

###### Proof of Theorem B.3.

Johnson et al. [17] observed that an $\alpha$-approximation algorithm for the
$k$-MST problem guarantees an $\alpha$-approximation also for EQ-URAT. This
observation, along with the $2$-approximation algorithm by Garg [9] for the
$k$-MST problem result in a $2$-approximation algorithm for EQ-URAT.
Therefore, by Lemma B.3, the theorem follows. ∎

### Maximum Weighted Budgeted Connected Set Cover (MWBCSC).

Let $X$ be a set of elements, $\mathcal{S}\subseteq 2^{X}$ be a collection
sets, $p:X\rightarrow\mathbb{R}^{+}$ be a prize function,
$c:\mathcal{S}\rightarrow\mathbb{R}^{+}$ be a cost function, $G_{\mathcal{S}}$
be a graph on vertex set $\mathcal{S}$, and $B$ be a budget. In MWBCSC, the
goal is to find a subcollection $\mathcal{S}^{\prime}\subseteq\mathcal{S}$
such that $c(\mathcal{S}^{\prime})=\sum_{S\in\mathcal{S}^{\prime}}c(S)\leq B$,
the subgraph induced by $\mathcal{S}^{\prime}$ is connected and
$p(\mathcal{S}^{\prime})=\sum_{x\in X_{\mathcal{S}^{\prime}}}p(x)$ is
maximized, where
$X_{\mathcal{S}^{\prime}}=\bigcup_{S\in\mathcal{S}^{\prime}}S$. Note that, as
MWBCSC coincides with the unrooted version of URAT when no two sets share an
element, MWBCSC admits no $o(\log\log n)$-approximation algorithm unless
$NP\subseteq DTIME(n^{\text{polylog}(n)})$ even if the budget constraint is
violated by a factor of any universal constant $\rho$ [21]. Moreover, since
the prize function of MWBCSC is submodular w.r.t. subsets of nodes, our
algorithm for the undirected unrooted version of DRSO guarantees an
$O(\sqrt{B})$-approximation for MWBCSC.

Consider the following assumption.

######  Assumption B.1.

Two sets $S$ and $S^{\prime}$ having an element in common are adjacent in
$G_{\mathcal{S}}$.

Denote by UAT the unrooted version of URAT. Ran et al. [29] provided a
$\frac{2(\Delta+1)\alpha}{1-e^{-1}}$-approximation algorithm for MWBCSC under
Assumption B.1, where $\alpha$ is the performance ratio for the algorithm used
to approximate UAT. Note that the best known algorithm for UAT is an
$O(\log{n})$-approximation [2]. Let $f$ be the maximum frequency of an element
in an instance of MWBCSC. Clearly, in the work by Ran et al. [29], $\Delta\geq
f$ as the authors investigated MWBCSC under Assumption B.1. In the following,
we aim to provide some approximation results for some variants of MWBCSC.

We first show that there exists a polynomial-time $\alpha f$-approximation
algorithm for MWBCSC (without Assumption B.1), where $\alpha$ is the
performance ratio of an algorithm for UAT.

######  Theorem B.4.

MWBCSC admits a polynomial-time $\alpha f$-approximation algorithm, where $f$
is the maximum frequency of an element and $\alpha$ is the performance ratio
of an algorithm for UAT.

###### Proof.

Let $I=(X,\mathcal{S},c,p,G_{\mathcal{S}}=(\mathcal{S},E_{S}),B)$ be an
instance MWBCSC. We create an instance $J=(G_{\mathcal{S}},c,p^{\prime},B)$ of
UAT, where $p^{\prime}(S)=\sum_{x\in S}p(x)$ for each $S\in\mathcal{S}$, that
results in loosing an approximation factor $f$.

Let $T$ be the solution returned by an $\alpha$-approximation algorithm for
UAT applied to $J$, $X_{T}=\cup_{S\in V(T)}S$, $OPT_{I}$, and $OPT_{j}$ be
optimal solutions for $I$ and $J$, respectively.

We have $p^{\prime}(T)\geq\frac{1}{\alpha}p^{\prime}(OPT_{J})$,
$p(OPT_{I})\leq p^{\prime}(OPT_{I})\leq p^{\prime}(OPT_{J})$, and

$\displaystyle p^{\prime}(T)=\sum_{S\in V(T)}\sum_{x\in S}p(x)=\sum_{x\in
X_{T}}|\\{S\in V(T):x\in S\\}|p(x)\leq f\sum_{x\in X_{T}}p(x)=fp(V(T)).$

Therefore,

$\displaystyle p(V(T))\geq\frac{1}{f}p^{\prime}(T)\geq\frac{1}{\alpha
f}p^{\prime}(OPT_{J})\geq\frac{1}{\alpha f}p^{\prime}(OPT_{I}).$

This implies that $V(T)$ is an $\alpha f$-approximation for $I$. ∎

Since the algorithm by Bateni et al. for UAT guarantees an $O(\log
n)$-approximation, where $n$ is the number of nodes in the graph, then MWBCSC
admits a polynomial-time $O(f\log{|\mathcal{S}|})$-approximation algorithm.

In the next step, we show that MWBCSC admits a $2f$-approximation algorithm
when each set has cost $1$. Note that this variant of MWBCSC has some
applications, e.g., the detection of mutated pathways in cancers [14, 31] and
wireless sensor networks [7, 16, 22, 29, 32, 33].

######  Theorem B.5.

When each set costs $1$, MWBCSC admits a polynomial-time $2f$-approximation
algorithm, where $f$ is the maximum frequency of an element.

###### Proof.

We observe that URAT when each vertex costs $1$ is equivalent to E-URAT when
each edge costs $1$ from an approximation point of view. Indeed, each tree
with at most $B-1$ edges includes at most $B$ nodes and vice-versa. The same
holds for the unrooted versions of URAT and E-URAT, which we call UAT and
E-UAT, respectively. Moreover, E-UAT admits a $2$-approximation algorithm that
consists in guessing the root and applying the 2-approximation algorithm for
E-URAT by Paul et al. [28]. Therefore, we have a $2$-approximation algorithm
for UAT and the theorem follows by Theorem B.4. ∎

In the next step, we will provide an approximation algorithm for MWBCSC which
does not depend on $f$. Recall that in a node-weighted graph $G$, for any two
vertices $u,v$, $dist(u,v)$ is the minimum cost of a path $P$ from $u$ to $v$,
where the cost of $P$ is the sum of the costs of its nodes. Now we show the
following.

######  Theorem B.6.

Let $\mathcal{A}$ be an $\alpha$-approximation algorithm for UAT. MWBCSC
admits a polynomial-time bicriteria $(h+1,\alpha)$-approximation algorithm,
where $h=\max_{\begin{subarray}{c}S,S^{\prime}\in\mathcal{S}\\\ S\cap
S^{\prime}\neq\emptyset\end{subarray}}(dist(S,S^{\prime})-(c(S)+c(S^{\prime})))$
such that $c(S)\geq 1,\forall{S\in\mathcal{S}}$.

To prove Theorem B.6, we need some observations and materials. Let
$I=(X,\mathcal{S},c,p,G_{\mathcal{S}},B)$ be an instance MWBCSC. Now we show
that one can transform an instance $I$ of MWBCSC to an instance of
$J=(G^{\prime}=(V^{\prime},E^{\prime}),c^{\prime},p^{\prime},B)$ of UAT. From
$G_{\mathcal{S}}=(V(G_{\mathcal{S}}),E(G_{\mathcal{S}}))$, we create graph a
$G^{\prime}=(V^{\prime},E^{\prime})$ as follows:
$V^{\prime}=V_{\mathcal{S}}\cup V_{X}$, where $V_{\mathcal{S}}=\\{v_{S}:S\in
V(G_{\mathcal{S}})\\}$ and $V_{X}=\\{v_{x}:x\in X\\}$, and
$E^{\prime}=E(G_{\mathcal{S}})\cup\\{\\{v_{S},v_{x}\\}:x\in S\\}$. We set for
any $v_{S}\in V_{\mathcal{S}}$, $p^{\prime}(v_{S})=0$ and
$c^{\prime}(v_{S})=c(S)$. For any $v_{x}\in V_{X}$, $p^{\prime}(v_{x})=p(x)$
and $c^{\prime}(v_{x})=0$.

######  Lemma B.4.

Let $SOL_{J}$ be a solution to UAT on the instance $J$. From $SOL_{J}$, a
solution $SOL_{I}$ to MWBCSC on instance $I$ can be obtained such that
$p(SOL_{I})\geq p^{\prime}(SOL_{J})$ and $c(SOL_{I})\leq(h+1)B$.

###### Proof.

Let $Sol^{\prime}=\emptyset$. We repeat the following process: if there exist
two edges $\\{v_{S},v_{x}\\},\\{v_{S^{\prime}},v_{x}\\}\in
E^{\prime}(SOL_{J})$, then
$Sol^{\prime}=Sol^{\prime}\cup\\{v_{S},v_{S^{\prime}}\\}$, where
$\\{v_{S},v_{S^{\prime}}\\}$ is an edge. Let $G(Sol^{\prime})$ be the graph
with edges in $Sol^{\prime}$. Let $\bar{T}=(V(\bar{T}),E(\bar{T}))$ be a
spanning tree of $G(Sol^{\prime})$. Note that we have $|E(\bar{T})|\leq B-1$
as $c(S)\geq 1,\forall{S\in\mathcal{S}}$. Note that if there exist two edges
$\\{v_{S},v_{x}\\},\\{v_{S^{\prime}},v_{x}\\}\in E^{\prime}(SOL_{J})$, where
$v_{S}\neq v_{S^{\prime}}$, there is a path $P$ of distance at most
$h+c(v_{S})+c(v_{S^{\prime}})$ between $v_{S},v_{S^{\prime}}\in
G_{\mathcal{S}}$. Let $SP_{e}$ be a shortest path on $G_{\mathcal{S}}$
connecting $e=\\{v_{S},v_{S^{\prime}}\\}$. Let
$Sol^{\prime\prime}=\\{SP_{e}:e\in E(\bar{T})\\}$ and $G(Sol^{\prime\prime})$
is a graph with edges in $Sol^{\prime\prime}$. $G(Sol^{\prime\prime})$ is a
connected subgraph of $G_{\mathcal{S}}$. Let $SOL_{I}$ be a spanning tree of
$G(Sol^{\prime\prime})$. This means that $c(SOL_{I})\leq B+(B-1)h\leq(h+1)B$
as $c(\bar{T})\leq B$ and $|E(\bar{T})|\leq B-1$ and each edge $e$ of
$G(Sol^{\prime})$ is replaced by a path $SP_{e}$ of cost at most $h$ in
$SOL_{I}$. Also, note that $p(SOL_{J})=\sum_{v_{x}\in V_{X}\cap
V^{\prime}(SOL_{J})}p(v_{x})$ as vertices in $V_{\mathcal{S}}\cap V^{\prime}$
has prize zero in $J$. So, we have $p^{\prime}(SOL_{I})\geq p(SOL_{J})$ as
$SOL_{I}$ spans all vertices in $Sol^{\prime\prime}$ and $Sol^{\prime\prime}$
spans all vertices in $Sol^{\prime}$. Hence a feasible solution (with at least
the same prize as $SOL_{J}$ and cost no more than $(h+1)B$) can be obtained
from $SOL_{J}$ for MWBCSC. This concludes the lemma. ∎

######  Observation B.1.

Let $J=(G^{\prime}=(V^{\prime},E^{\prime}),c^{\prime},p^{\prime},B)$ be an
instance of UAT resulting in our transformation from an instance
$I=(X,\mathcal{S},c,p,G_{\mathcal{S}},B)$ of MWBCSC. Let $OPT_{J}$ and
$OPT_{I}$ be optimal solutions to $J$ and $I$, respectively. Then
$p(OPT_{J})\geq p(OPT_{I})$.

###### Proof.

From any solution $T$ to $I$ where $c(T)\leq B$, we can always create a
solution $T^{\prime}$ to $J$ by our transformation, where
$c(T^{\prime})=c(T)=B$ and $p(T^{\prime})=p(T)$. This means that we never have
the case where $p(OPT_{J})<p(OPT_{I})$, otherwise by transforming $OPT_{I}$ to
a solution for $J$, we can achieve a better solution for $J$, which
contradicts the assumption that $OPT_{J}$ is an optimal solution to $J$. This
concludes the proof.∎

Now we are ready to prove Theorem B.6.

###### Proof of Theorem B.6.

Let $OPT_{J}$ and $OPT_{I}$ be the optimum solutions to $J$ and $I$,
respectively. By Lemma B.4 and Observation B.1, any $\alpha$-approximation for
UAT results in a solution $SOL_{I}$ for MWBCSC such that
$p(SOL_{I})\geq\frac{OPT_{J}}{\alpha}\geq\frac{OPT_{I}}{\alpha}$ and
$c(SOL_{I})\leq(h+1)B$. ∎

######  Corollary B.1.

One can have a polynomial-time $O(h\log{n})$-approximation algorithm for
MWBCSC, when $c(S)\geq 1,\forall{S\in\mathcal{S}}$.

###### Proof.

Note that Bateni et al. [2]’s approach for the prize collecting problem and
the black-box introduced by Moss and Rabbani [26] result in an $O(\log
n)$-approximation algorithm for UAT violating the budget constraint by a
factor of $2$. We call this approach BMAlg. Let $T$ be such a solution after
applying BMAlg, where $c(T)\leq 2B$ and $p(T)=O(p(OPT))$ that $OPT$ is an
optimal solution to UAT. Then Bateni et al. [2] provided a trimming process to
achieve a solution $T^{\prime}\subseteq T$ which has cost $c(T^{\prime})\leq
B$ by loosing some constant in the approximation factor.

Note that as in MWBCSC the prize function is monotone submodular, we need to
use our trimming process (i.e., Lemma 5.1). Now we follow the same argument as
that of Theorem 5.1. This means that we first restrict our-self to flat trees
by guessing the vertex $x$ with the maximum cost, setting the budget
$B=B-c(x)$ and removing vertices with cost more that $B/2$. Next we transform
the instance $I$ of MWBCSC to the instance $J$ of UAT as above. Now by BMAlg,
we can achieve a solution $SOL_{J}$ to $J$ such that $p(SOL_{J})=O(\log n)$
and $c(SOL_{J})\leq 2B$. We then transform $SOL_{J}$ to a solution for $I$,
denoted by $SOL_{I}$ as Lemma B.4. Hence $p(SOL_{I})=O(\log n)$ and
$c(SOL_{I})\leq 2B(h+1)$. Finally, we apply Lemma 5.1 to achieve an out-
subtree $\hat{T}$ of $SOL_{I}$ with the cost $B/4\leq c(\hat{T})\leq B$ and
the prize-to-cost ratio
$\frac{p(\hat{T})}{c(\hat{T})}\geq\frac{\gamma}{32(2B(h+1))+8}$. This implies
that $p(\hat{T})=O(\frac{1}{h\log n})$.∎

Another important consequence of Theorem B.6 is that $\alpha$-approximation
algorithm for UAT yields an $\alpha$-approximation algorithm for MWBCSC under
Assumption B.1. This is an improvement over
$\frac{2(\Delta+1)\alpha}{1-e^{-1}}$-approximation algorithm of Ran et al.
[29], where $\Delta$ is the maximum degree of the graph. Note that in this
case we do not need to assume that $c(S)\geq 1,\forall{S\in\mathcal{S}}$.

######  Corollary B.2.

One can have a polynomial-time $O(\log{n})$-approximation algorithm for MWBCSC
under Assumption B.1.

###### Proof.

Let $J=(G^{\prime}=(V^{\prime},E^{\prime}),c^{\prime},p^{\prime},B)$ be an
instance of UAT resulting in our transformation from an instance
$I=(X,\mathcal{S},c,p,G_{\mathcal{S}},B)$ of MWBCSC. Now we run the algorithm
by Bateni et al. on $J$. Let $SOL_{J}$ be the solution that returned by their
approach, where $c(SOL_{J})\leq B$ and $p(SOL_{J})=O(\log n)$. We know that if
there exist two edges $\\{v_{S},v_{x}\\},\\{v_{S^{\prime}},v_{x}\\}\in
E(SOL_{J})$, then $S$ and $S^{\prime}$ are neighbor in $G_{\mathcal{S}}$ (by
Assumption B.1). So, we can obtain a solution
$SOL_{I}=(V(SOL_{I}),E(SOL_{I}))$ for MWBCSC form $SOL_{J}$ with the same cost
and prize. ∎

Last we show that there is a polynomial-time constant approximation algorithm
for MWBCSC when each set costs one under Assumption B.1.

######  Theorem B.7.

Under Assumption B.1, MWBCSC admits a polynomial-time
$\frac{16}{1-e^{-1}}$-approximation algorithm, when each set has cost one.

We need one useful observation.

######  Lemma B.5 (Lemma 3 in Lamprou et al. [23]).

Let $k$ be an integer. Given any tree $T$ on $ak$ vertices, where $a\in N$ is
a constant, and $k\geq 4a-2$, we can decompose it into $2a$ subtrees each on
at most $k$vertices.

We are ready to prove Theorem B.7.

###### Proof.

Let $I=(X,\mathcal{S},c,p,G_{\mathcal{S}},B)$ be an instance MWBCSC. Ran et
al. [29] showed that there exists a connected subcollection of
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that
$p(\mathcal{S}^{\prime})\geq\frac{1-e^{-1}}{2}opt$ and
$c(\mathcal{S}^{\prime})\leq 2B$, where $opt$ is the optimum solution. As in
our case each vertex in $G_{\mathcal{S}}$ has cost $1$, by the same argument
as that of Theorem B.5, we can set the budget to $2B-1$ and run the
polynomial-time $2$-approximation algorithm of Paul et al. [28] on this input.
This provides us a tree $T=(V(T),E(T))$ with $|E(T)|\leq 2B-1$ and
$p(T)\geq\frac{1-e^{-1}}{4}opt$. By Lemma B.5, we can decompose $T$ into $4$
subtrees each containing at most $B$ vertices. This concludes the proof. ∎

### Budgeted Sensor Cover Problem (BSCP).

This problem is very well-known in wireless sensor networks. In BSCP, we are
given a set $\mathcal{S}$ of sensors, a set $\mathcal{P}$ of target points in
a metric space, a sensing range $R_{s}$, a communication range $R_{c}$, and a
budget $B$. A target point is covered by a sensor if it is within distance
$R_{s}$ from it. Two sensors are connected if they are at a distance at most
$R_{c}$. The goal is to find a subset
$\mathcal{S}^{\prime}\subseteq\mathcal{S}$ such that
$|\mathcal{S}^{\prime}|\leq B$, the number of covered target points by
$\mathcal{S}^{\prime}$ is maximized and $\mathcal{S}^{\prime}$ induces a
connected subgraph.

Note that BSCP is a special case of MWBCSC and then, by Theorem B.5, we have a
$2f$-approximation algorithm for BSCP, where $f$ is the maximum number of
sensors that cover a target point.

Next we investigate BSCP under the widely used assumption that $R_{s}\leq
R_{c}/2$, where $R_{s}$ and $R_{c}$ are the sensing range and communication
range of sensors, respectively. In the following, we show that using some
materials from the literature leads to an improvement to [16, 22, 29, 32, 33]
for BSCP under the assumption that $R_{s}\leq R_{c}/2$. Note that Huang et al.
[16] studied BSCP under the assumption that $R_{s}/R_{c}=O(1)$, however, our
result improves their result under the assumption that $R_{s}\leq R_{c}/2$.

######  Theorem B.8.

If $R_{s}\leq R_{c}/2$, then BSCP admits a polynomial-time
$\frac{8}{1-e^{-1}}$-approximation algorithm.

###### Proof.

We first construct a graph $G=(V,E)$ as follows: $V=\mathcal{S}$ and for any
two sensors $s,s^{\prime}\in\mathcal{S}$, $e=(s,s^{\prime})\in E$ if
$d(s,s^{\prime})\leq R_{c}$, where $d$ denotes the minimum distance between
two senors $s$ and $s^{\prime}$ in the plane. Now we assign prizes to the
nodes in $G$ as follows: we iteratively pick the sensor $s$ that covers the
maximum number of the target points in the plane, assign the number of the
covered target points to $s$ as its prize and remove $s$ and the covered
target points from further consideration. It can be shown that assigning
prizes to the nodes in such a way ensures that $G$ contains a connected
subgraph $G^{\prime}$, $G^{\prime}\subseteq G$, with $|V(G^{\prime})|\leq 2B$
and the prize $p(G^{\prime})\geq(1-e^{-1})opt$, where $opt$ is the optimum to
BSCP (see e.g. [7, 29]).

From the proof of Theorem B.5, we only need to consider the unrooted version
of E-URAT where the input graph is $G$ with cost $1$ on the edges and budget
$2B-1$. Now we apply the polynomial-time $2$-approximation algorithm of Paul
et al. [28] to this input and achieve a tree $T$ of cost at most $2B-1$ and
prize at least $p(T)\geq\frac{1-e^{-1}}{2}opt$. By Lemma B.5, we can decompose
$T$ into $4$ subtrees each containing at most $B$ vertices and select the one
with the maximum prize. This concludes the proof. ∎