1 Introduction↩︎

We study the problem of Connected Submodular Maximization (CSM). In this problem, we are given an undirected graph \(G= (V, E)\) with \(n\) vertices and \(m\) edges, a non-negative monotone submodular set function \(f\) whose ground set is \(V\), and an integer \(k\geq 1\); the goal is to select a tree \(S\subseteq G\), with \(k\) edges, whose vertex set maximizes \(f\).¹ We also study Directed Connected Submodular Maximization (DCSM), which generalizes CSM by letting \(G\) be a directed graph; the goal is to select an out-tree (i.e., arborescence) \(S\subseteq G\), with \(k\) edges, whose vertex set maximizes \(f\). We further study Directed Rooted Connected Submodular Maximization (DRCSM), which generalizes DCSM by specifying a vertex \(v\) to be the root of the selected out-tree.

CSM has received significant attention owing to its important applications. These include deploying a connected network, of limited size, with maximum coverage or throughput; specifically positioning a connected network of wireless routers or relays [1], [2], unmanned aerial vehicles [3]–[7], or wireless power chargers [8]–[10]. Another application of CSM is identifying a limited number of geographically connected regions that, if undervaccinated, are most susceptible to an epidemic outbreak [11]. This is motivated by the need for public health interventions, which are most effective within a small number of localized undervaccinated regions. Further, CSM is related to maintaining a communication network between robots in multi-robot task planning [12].

An important special case of CSM is Connected Maximum Coverage (CMC). Here, we are given a universe of elements \(X\), an undirected graph \(G\) where each vertex is a subset of \(X\), and an integer \(k\geq 1\); the goal is to select a tree \(S\subseteq G\), with \(k\) edges, whose vertex set maximizes the number of its covered elements. CMC has application to deploying a wireless sensor network, of limited size, with maximum coverage [13]–[15]. CMC also has application to identifying genetic mutations associated with cancers [16], [17]. In this application, we are given a universe of cancer patients and a gene interaction network, wherein each genetic mutation is associated with the subset of patients that have the mutation. As cancer is widely assumed to be caused by a network of mutated genes (called a pathway), the goal is to select a limited set of connected gene mutations that ‘explain’ the most cases of cancer (i.e., cover the most patients). CMC is also related to the Watchman Route Problem, where we are given a ‘map’ of various locations, and the goal is to find a minimum-length path in the map such that every location is visible from somewhere along the path [18], [19]. Further, Directed Rooted Connected Maximum Coverage (DRCMC), i.e., the special case of DRCSM with a coverage objective, is related to problems where we are given a network that models interactions between agents, and the goal is to select a minimum-size rooted out-tree that reconstructs the propagation of some activity throughout the network, such as an epidemic outbreak [20], [21].

Approximation Algorithms.

Most of the previous works on CSM have focused on polynomial time approximation algorithms. CSM was first studied by Kuo et al. [1], where they showed a polynomial time \(\frac{1-1/e}{5(\sqrt{k+1}+1)}\)-approximation algorithm. Xu et al. [3] improved the approximation factor to \(\frac{1-1/e}{\lfloor \sqrt{k+1} \rfloor}\), and Li et al. [5] further improved it to \(\Omega( \sqrt{ \frac{s}{k} })\), where \(s\) is a chosen integer parameter (their algorithm runs in polynomial time if \(s\) is set constant). Note that these works have only found constant-factor improvements in approximation. There also exists, for any constant \(\varepsilon> 0\), a polynomial time \(\Omega(\frac{1}{\log^{2+\varepsilon} n})\)-approximation algorithm for CSM as implied by Theorem 3.1 of Im et al. [22]. This, in turn, is implied by an algorithm for Polymatroid Steiner Tree due to Calinescu and Zelikovsky [23]. However, this algorithm crucially relies on taking a tree embedding of the input graph, which does not work for general directed graphs.

We also mention that a number of works have studied budgeted variants of (Directed Rooted) CSM [1], [24], [25] and (Directed Rooted) CMC [14], [15], [25]–[27], i.e., with edge or vertex costs. We outline these works in the related work (Section 5), though we mention the state-of-the-art works on budgeted (Directed Rooted) CSM here. Ghuge and Nagarajan [24] studied DRCSM with edge costs, showing a quasi-polynomial time \(\Omega(\frac{\log \log k'}{\log k'})\)-approximation algorithm, where \(k'\) is the number of vertices in an optimal tree. D’Angelo et al. [25] studied (Directed) CSM and DRCSM with vertex costs, showing polynomial time algorithms: letting \(B\) denote the budget, they respectively gave a \(\Omega(\frac{1}{\sqrt{B}})\)-approximation algorithm and, for every \(\delta\in (0, 1]\), a \(\Omega(\frac{\delta^{3}}{\sqrt{B}})\)-approximation algorithm that violates the budget by at most a factor of \(1+\delta\).

Despite the aforementioned approximation algorithms, there appear to be no interesting approximation hardness results for CSM. The most we can say is that it is NP-hard to find an approximation better than \(1-\frac{1}{e}\) [28], since the cardinality constrained problem is a special case (by taking a complete graph as input). However, for budgeted variants of CSM, there are near-logarithmic approximation hardness results [29]–[31]. We outline these hardness results in the related work (Section 5).

Radius-Sensitive Approximation Algorithms.

Previous works have also considered polynomial time algorithms for CSM whose approximation factors depend on one or more parameters that restrict the input graph, \(G\), or the input function, \(f\). These algorithms are useful as, for certain parameter values, they can outperform algorithms whose approximation factors depend on \(n\) or \(k\). In this paper, we are interested in the radius of the optimal (out-)tree, denoted by \(r\). Other parameters that have been considered in the approximation factor include the doubling dimension of a metric graph [11], the curvature of \(f\) [6], and the \(h\)-hop independence of \(f\) [4], [6].

For an instance of CSM, we define the radius, \(r\), of an optimal tree. First, let \(v\) be the center of the optimal tree, i.e., \(v\) is the vertex that minimizes its maximum shortest distance to any other vertex in the optimal tree. Then \(r\) is this maximum distance. For an instance of DCSM or DRCSM, we define the radius, \(r\), of an optimal out-tree to be equivalent to its height, i.e., the number of edges in the longest directed path from its root. Note that \(r\leq \lceil \frac{k}{2} \rceil\) holds for an undirected tree and \(r\leq k\) for a directed out-tree.

The optimal solution radius \(r\) is a natural parameter to consider as a smaller \(r\) makes the vertices of an optimal (out-)tree more reachable from its center \(v\), thus enabling better approximations. To see this intuitively, suppose \(r= 1\); in this case, we can guess \(v\), initialize our solution with it, and then run the standard greedy algorithm on the (out-)neighbors of \(v\). This achieves a \((1-\frac{1}{e})\)-approximation, the same as for the cardinality constrained variant [32]. Moreover, the optimal solution radius is expected to be small in ‘small-world’ graphs, which are graphs where the average shortest distance between a pair of vertices is \(O(\log n)\).

Although the optimal solution radius \(r\) is a natural parameter, only two previous works have studied it in the approximation factor for CSM or the special case Connected Maximum Coverage (CMC), both achieving \(\Omega(\frac{1}{r})\)-approximations. Vandin et al. [16] first showed a polynomial time \(\frac{e-1}{(2e-1)r}\)-approximation algorithm for CMC. Hochbaum and Rao [17] improved this approximation by a constant factor to \(\max\{ (1 - \frac{1}{e} ) ( \frac{1}{r} - \frac{1}{k+1} ), \frac{1}{k+1} \}\) and extended their result to CSM. However, observe that when \(r= \Theta(k)\), these algorithms only achieve a \(\Omega(\frac{1}{k})\)-approximation, the same as the trivial approximation achieved by selecting the most valuable vertex in \(G\). Thus, it would be ideal to achieve a unified approximation with the same dependence on \(r\) and \(k\), asymptotically speaking.

1.1 Our Contributions↩︎

Our main result is Theorem 1 below.

Theorem 1 shows that, for every constant \(\varepsilon< \frac{1}{2}\), we improve on the previous polynomial time \(\Omega(\frac{1}{\sqrt{k}})\)-approximations [1], [3], [5] (recalling that \(r\leq k\)). Moreover, for every constant \(\varepsilon< 1\), we improve on the previous polynomial time \(\Omega(\frac{1}{r})\)-approximations [16], [17].

We also obtain Theorem 2 for the more general problem of Directed Rooted Connected Submodular Maximization (DRCSM). This theorem gives a bicriteria \((\alpha, \beta)\)-approximation algorithm, which is an algorithm that outputs an \(\alpha\)-approximate solution that may violate the size constraint by at most a factor of \(\beta\geq 1\).

Our Algorithmic Framework.

Our framework for achieving Theorems 1 and 2 involves combining two novel algorithms for DRCSM, namely GreedyRadius and RecApprox-\(d\), whose guarantees we outline below.

GreedyRadius takes a bicriteria \((\alpha(k), \beta(k))\)-approximation algorithm for DRCSM that runs in time \(\Gamma(n, k)\) and outputs a bicriteria \(( \frac{1}{2} \alpha(r), 4\beta(r) )\)-approximation in time \(O(\frac{kn}{r} \Gamma(n, r))\); we formally state these guarantees in Theorem 3. By selecting a valuable size-\(k\) out-subtree of this solution, we obtain a feasible \(\frac{\alpha(r)}{16\beta(r)}\)-approximation for (Directed) CSM; we formally state this result in Corollary 3. Alternatively, by applying a simple trimming process, we obtain a bicriteria \((\frac{\delta\alpha(r)}{16 \beta(r)}, 1+\delta)\)-approximation for DRCSM; we formally state this result in Corollary 5.

We further propose RecApprox-\(d\) as an algorithm that can be used as a subroutine in our framework. For every integer \(d\geq 1\), RecApprox-\(d\) is a bicriteria \((\frac{1}{d+1}, (d+1)^{2} k^{\frac{1}{d}})\)-approximation algorithm for DRCSM that runs in time \(O(n^{d+1} k^{2d+2})\). We formally state the performance guarantees of RecApprox-\(d\) in Theorem 6.

By running GreedyRadius with subroutine RecApprox-\(d\), we obtain a bicriteria \((\frac{1}{2(d+1)}, 4(d+1)^{2} r^{\frac{1}{d}})\)-approximation algorithm for DRCSM that runs in time \(O(kn^{d+2} r^{2d+1})\). Then, by selecting a size-\(k\) out-subtree (Corollary 3), we obtain a feasible \(\frac{1}{16(d+1)^{3} r^{1/d}}\)-approximation for (Directed) CSM. Otherwise, by the trimming process (Corollary 5), we obtain a bicriteria \((\frac{\delta}{16 (d+1)^{3} r^{1/d}}, 1+\delta)\)-approximation for DRCSM. We assign \(d= \lceil \frac{1}{\varepsilon}\rceil\) in the above approximation factors and use the bounds \(\frac{1}{\varepsilon} \leq \lceil \frac{1}{\varepsilon} \rceil \leq \frac{1}{\varepsilon} + 1\) to derive Theorems 1 and 2 respectively.

In general, we can plug any algorithm for DRCSM into our framework to convert its (bicriteria) approximation factor’s dependence on \(k\) to \(r\). For example, we can plug in the quasi-polynomial time \(\Omega(\frac{\log \log k}{\log k})\)-approximation algorithm by Ghuge and Nagarajan [24] to achieve a bicriteria \((\Omega(\frac{\log \log r}{\log r}), 4)\)-approximation.

1.2 Technical Overview↩︎

Here we outline the main ideas used in GreedyRadius and RecApprox-\(d\), while comparing with previous approaches. Both of our algorithms aim to construct an out-tree for DRCSM by greedily combining valuable out-subtrees, rather than valuable vertices, along with connecting paths from the root vertex.

GreedyRadius.

We first explain why the previous-best algorithm [17] only achieves a \(\Omega(\frac{1}{r})\)-approximation for CSM. This algorithm first initializes a solution, \(S\), with the root \(v\), and then uses the following greedy approach. While \(S\) can be feasibly updated: (1) find a vertex, \(\hat{w}\), of distance at most \(r\) from \(v\), whose shortest path from \(v\) has maximum marginal gain to \(S\), and (2) add this shortest \(v\)–\(\hat{w}\) path to \(S\). The issue here is that, for a given \(\hat{w}\), there may be many shortest \(v\)–\(\hat{w}\) paths (which cannot all be considered in polynomial time). This means it is possible for the algorithm to just add \(v\)–\(\hat{w}\) paths in which the only valuable vertex is \(\hat{w}\). Thus, it may incur up to \(r\) edges to add each valuable vertex to the solution.

To improve on the above approach, GreedyRadius constructs a solution \(S\) by greedily adding valuable out-subtrees. GreedyRadius constructs each added out-subtree by guessing the root, \(\hat{w}\), of a valuable size-\(r\) out-subtree, \(\hat{T}\), of the optimal out-tree; then it calls the given \((\alpha(k), \beta(k))\)-approximation subroutine to solve a sub-instance of DRCSM with size constraint \(r\) and the guess of root \(\hat{w}\). The subroutine must output an \((\alpha(r), \beta(r))\)-approximation of \(\hat{T}\). By combining sufficiently many of these out-subtrees, along with connecting paths of length at most \(r-1\), the solution \(S\) is a \((\frac{1}{2}\alpha(r), 4\beta(r))\)-approximate out-tree.

RecApprox-\(d\).

RecApprox-\(d\) is a procedure that initializes our main recursive algorithm, RecApprox, so that the maximum depth of its recursion tree (counted by ‘edges’) is \(d\); we call \(d\) the recursion depth of RecApprox-\(d\). Note that we use \(b\) to denote the size constraint of a sub-instance of DRCSM to distinguish it from the size constraint, \(k\), of a main instance of DRCSM.

RecApprox uses a recursive greedy strategy that generalizes the strategy by Kuo et al. [1] for implicitly achieving a bicriteria \((1 - \frac{1}{e}, b)\)-approximation for DRCSM (which they used to achieve an overall \(\Omega(\frac{1}{\sqrt{k}})\)-approximation for CSM). We explain the basic approach of Kuo et al. [1] first: given an instance of DRCSM with size constraint \(b\) and root \(v\), initialize a solution, \(S\), with the root \(v\). Then greedily add \(b\) vertices, of distance at most \(b\) from \(v\), to \(S\), along with connecting paths from \(v\).

To implement a recursive greedy strategy, RecApprox takes in its input a value \(q> 1\); this is to reduce the size constraint to at most \(\frac{b}{q}\) in the recursive calls. Then RecApprox constructs a solution \(S\) by greedily adding valuable out-subtrees. RecApprox constructs each added out-subtree by guessing the size, \(\hat{c}\leq \frac{b}{q}\), and root, \(\hat{w}\), of a valuable out-subtree, \(\hat{T}\), of the optimal out-tree; then it makes a recursive call to solve a sub-instance of DRCSM with the guesses of size \(\hat{c}\) and root \(\hat{w}\). RecApprox continues adding valuable out-subtrees until the sum of their corresponding size-guesses is \(b\). RecApprox also adds connecting paths of length at most \(b- 1\).

Lastly, to achieve the bicriteria \((\frac{1}{d+1}, (d+1)^2 k^{\frac{1}{d}})\)-approximation for DRCSM, RecApprox-\(d\) calls RecApprox with size constraint \(k\), root \(v\), and value \(q= k^{\frac{1}{d}}\), and returns the solution output by RecApprox. We can see that the assignment of \(q= k^{\frac{1}{d}}\) ensures a recursion depth of \(d\) since it makes the size constraints in a chain of recursive calls at most \(k^{\frac{d}{d}}, k^{\frac{d-1}{d}}, \dots, k^{\frac{1}{d}}, k^{\frac{0}{d}}\).

We point out that RecApprox uses a similar recursion to an existing algorithm by Calinescu and Zelikovsky [23] for the problem of Polymatroid Directed Steiner Tree. Using additional ideas, it is possible to adapt their algorithm to achieve a bicriteria approximation for DRCSM similar to that of RecApprox, but the resulting running time is worse than that of RecApprox by a polynomial factor. We compare our algorithm with theirs and sketch how to adapt it for DRCSM in the related work (Section 5).

1.3 Paper Structure↩︎

We present preliminaries in Section 2, GreedyRadius in Section 3, RecApprox and RecApprox-\(d\) in Section 4, related work in Section 5, and conclusions in Section 6.

2 Preliminaries↩︎

In this paper, \(G\) denotes an undirected or directed graph, \(V(G)\) denotes the vertex set of \(G\), and \(E(G)\) denotes the edge set of \(G\). Define functions \(n(G) \mathrel{\vcenter{:}}= |V(G)|\), which is the cardinality of \(G\), and \(m(G) \mathrel{\vcenter{:}}= |E(G)|\), which is the size of \(G\). If \(G\) refers to the input graph of our problem, we simply use \(V\), \(E\), \(n\), and \(m\) to denote the vertex set, edge set, cardinality, and size of \(G\) respectively.

Given an undirected or directed graph \(G\), the distance from vertex \(v\) to vertex \(w\), \(\mathop{\mathrm{dist}}_{G}(v, w)\), is the number of edges in a shortest (directed) path from \(v\) to \(w\). If \(G\) refers to the graph in the problem input, we may simply use \(\mathop{\mathrm{dist}}(v, w)\) to denote the distance from \(v\) to \(w\).

Undirected Graph Terms.

Given an undirected graph \(T\), the eccentricity of a vertex \(v\in V(T)\), \(\epsilon_{T}(v)\), is the maximum distance from \(v\) to \(w\) over all \(w\in V(T)\); that is, \(\epsilon_{T}(v) \mathrel{\vcenter{:}}= \max_{w\in V(T)} \mathop{\mathrm{dist}}_{T}(v, w)\).

The radius, \(r\), of \(T\) is the minimum eccentricity over all \(v\in V(T)\); that is, \(r= \min_{v\in V(T)} \epsilon_{T}(v)\). A center of \(T\) is a vertex \(v\in V(T)\) whose eccentricity is equal to the radius (there can be more than one center).

Directed Graph Terms.

A directed graph \(T\) is an out-tree (i.e., arborescence) if there exists a vertex \(v\in V(T)\) such that for every \(w\in V(T)\), there is exactly one directed path in \(T\) from \(v\) to \(w\). The vertex \(v\) is called the root of \(T\).

The radius (i.e., height), \(r\), of an out-tree \(T\) is the maximum distance from its root \(v\) to \(w\) over all \(w\in V(T)\); that is, \(r= \max_{w\in V(T)} \mathop{\mathrm{dist}}_{T}(v, w)\).

Submodular Functions.

Let \(f\) be a set function whose ground set is \(V\). Given subsets \(X, Y\subseteq V\), let \(f(X\mid Y) \mathrel{\vcenter{:}}= f(X\cup Y) - f(Y)\), which is called the marginal gain of \(X\) to \(Y\). As an abuse of notation, we may apply \(f\) to a subgraph \(S\subseteq G\), which means applying it to the vertex set of \(S\). Also, we may apply \(f\) to a single vertex \(v\in V\), which means applying it to the set \(\{ v\}\).

We consider functions \(f\) that are non-negative monotone submodular, as defined below.

A set function \(f\) is monotone iff for all \(X, Y\subseteq V\) where \(X\subseteq Y,\, f(X) \leq f(Y)\); and \(f\) is non-negative iff for all \(X\subseteq V,\, f(X) \geq 0\).

We make the standard assumption that \(f\) (or the marginal gain function) is queried via a value oracle; we specifically assume a strong value oracle, which allows both feasible and infeasible sets to be queried. For convenience, we analyze the running time of each algorithm by only counting the number of value oracle queries it makes.

Problem Definitions.

The problem of Connected Submodular Maximization (CSM) is defined as follows. We are given an undirected graph \(G= (V, E)\) with \(n\) vertices and \(m\) edges, a non-negative monotone submodular function \(f: 2^V\rightarrow \mathbb{R}_{\geq 0}\), and an integer \(k\geq 1\). The goal is to select a tree \(S\subseteq G\), with \(m(S) \leq k\), that maximizes \(f\).

The problem of Directed Connected Submodular Maximization (DCSM) generalizes CSM by letting \(G\) be a directed graph and additionally requiring that the selected \(S\subseteq G\) is an out-tree. The problem of Directed Rooted Connected Submodular Maximization (DRCSM) in turn generalizes DCSM by specifying a vertex \(v\) to be the root of the selected out-tree \(S\subseteq G\).

Note that we use \(k\) to constrain the size, i.e., number of edges, of \(S\). This is convenient for us since our analyses heavily rely on partitioning trees into edge-disjoint (out-)subtrees and constructing solutions out of edge-disjoint (out-)subtrees.

We use \(T^{*}\) to denote an optimal (out-)tree to any one of our problems, and \(v\) and \(r\) to denote its root and radius (height) respectively.

Bicriteria Approximation.

Let \(\alpha\in (0, 1]\) and \(\beta\geq 1\) be values, which we call the approximation factor and the violation factor respectively. Then, for any given instance of one of our problems, an \((\alpha, \beta)\)-approximation is a solution \(S\) with value \(f(S) \geq \alpha f(T^{*})\) and size \(m(S) \leq \beta k\). Further, for any one of our problems, an \((\alpha, \beta)\)-approximation algorithm returns an \((\alpha, \beta)\)-approximation for every instance of the problem.

Tree Partitioning.

Throughout our analyses, we use Lemma 1 below, which is a simplified version of Lemma 2 of Khani and Salavatipour [33].

3 GreedyRadius: Radius-Sensitive Approximation Algorithm↩︎

We present the algorithm GreedyRadius for DRCSM, with pseudocode in Algorithm 1 and performance guarantees in Theorem 3. We explain how to use GreedyRadius to achieve a feasible approximation for (Directed) CSM in Section 3.3 and a bicriteria approximation with \((1+\delta)\)-violation factor for DRCSM in Section 3.4.

3.1 Overview of GreedyRadius↩︎

GreedyRadius takes as input a directed graph \(G\), a non-negative monotone submodular function \(f\), a size constraint \(k\geq 1\), a root vertex \(v\), the optimal solution’s radius \(r\), and an \((\alpha(k), \beta(k))\)-approximation subroutine Alg; we assume that Alg takes an instance \((G, f, k, v)\) of DRCSM as input. GreedyRadius outputs an out-tree \(S\subseteq G\), with root \(v\), that \((\frac{1}{2} \alpha(r), 4\beta(r) )\)-approximates \(T^{*}\).

To give a high-level overview of how GreedyRadius works, we first assume \(T^{*}\) is partitioned into \(\Delta\leq \lfloor \frac{2 k}{r} \rfloor\) edge-disjoint out-subtrees, \(T^{*}_{1}, \dots, T^{*}_{\Delta}\), each of size at most \(r\) (Corollary 1). The roots of these out-subtrees are all of distance \(r-1\) from \(v\). GreedyRadius initializes the output solution, \(S\), with the root, \(v\), and updates it over \(t= \lfloor \frac{2 k}{r} \rfloor\) iterations. Let \(S_{\leq 0} = (\{v\}, \varnothing)\) and, for each \(i\in [1, t]\), let \(S_{\leq i}\) be the \(i\)th partial solution, \(\hat{T}_{i}\) be the out-subtree from \(T^{*}_{1}, \dots, T^{*}_{\Delta}\) with maximum marginal gain to \(S_{\leq i-1}\), and \(\hat{w}_{i}\) be the root of \(\hat{T}_{i}\). Then, in the \(i\)th iteration, GreedyRadius performs these steps: (1) guess \(w_{i} = \hat{w}_{i}\), (2) call Alg to construct an out-subtree \(S^{ w_{i} }_{i}\), with root \(w_{i}\), that \((\alpha(r), \beta(r))\)-approximates \(\hat{T}_{i}\), and (3) add \(S^{ w_{i} }_{i}\) and a \(v\)–\(w_{i}\) connecting path to \(S_{\leq i-1}\) to get \(S_{\leq i}\).

3.2 Analysis of GreedyRadius↩︎

Our main result is Theorem 3 below. The approximation factor follows from Lemma 2 and the violation factor follows from Lemma 3. The running time easily follows from GreedyRadius making at most \(\lfloor \frac{2k}{r} \rfloor n\) calls to both Alg and \(f\) (in the statement of Theorem 3, \(\Gamma(n, r)\) is the running time of Alg with an input graph \(G\) of \(n\) vertices, and size constraint \(r\)).

Analysis Notation for GreedyRadius.

We use the following notation based on the pseudocode of GreedyRadius (Algorithm 1). Recall that \(r\) denotes the radius of the optimal out-tree \(T^{*}\). Let \(t= \lfloor \frac{2 k}{r} \rfloor\) denote the total number of updates GreedyRadius makes in Line [line:GR32update32sol] to construct the output solution. Let \(S_{\leq 0} = ( \{ v\}, \varnothing)\) denote the initial state of the output solution as in Line [line:GR32init32sol], and \(S_{\leq i}\) denote the \(i\)th partial solution as in Line [line:GR32update32sol] of the \(i\)th iteration of the Line [line:GR32update32loop] loop. Further, let \(S^{w_{i}}_{i}\) denote the \(i\)th approximate out-subtree appended to the output solution, and \(P_{i}\) denote the path added to connect \(v\) to \(w_{i}\), the root of \(S^{w_{i}}_{i}\).

Partitioning the Optimal Solution for GreedyRadius.

First, an optimal out-tree \(T^{*}\) can be partitioned into edge-disjoint out-subtrees each of size at most \(r\) as in Corollary 1 below. This corollary directly follows from Lemma 1 by setting \(s= \frac{r}{2}\) and \(T= T^{*}\), where \(m(T^{*}) = k\).

Approximation Factor of GreedyRadius.

Violation Factor of GreedyRadius.

3.3 Feasible Approximation for (Directed) CSM↩︎

Here we explain how GreedyRadius can be used to achieve a feasible \(\frac{\alpha(r)}{16\beta(r)}\)-approximation for the problem of (Directed) CSM.

First, an out-tree \(S\) can be partitioned into out-subtrees as in Corollary 2 below. This corollary directly follows from Lemma 1 by setting \(s= \frac{k}{2}\) and \(T= S\), where \(m(S) \leq 4 \beta(r) k\).

Now we prove the required approximation result in Corollary 3, which follows from Theorem 3 and Corollary 2.

3.4 Bicriteria Approximation for DRCSM with \((1+\delta)\)-Violation Factor↩︎

Here we explain how GreedyRadius can be used to achieve, for every \(\delta\in [\frac{1}{k}, 1]\), a \(( \frac{\delta\alpha(r)}{16 \beta(r)}, 1 + \delta)\)-approximation for DRCSM.

First, an out-tree \(S\) can be partitioned into out-subtrees as in Corollary 4 below. This corollary directly follows from Lemma 1 by setting \(s= \frac{\delta k}{2}\) and \(T= S\), where \(m(S) \leq 4 \beta(r) k\).

Now we prove the required approximation result in Corollary 5, which follows from Theorem 3 and Corollary 4.

4 RecApprox-\(d\): Recursive Greedy Approximation Algorithm↩︎

We present the algorithm RecApprox for DRCSM, with pseudocode in Algorithm 2 and performance guarantees in Theorem 4. We also define RecApprox-\(d\) to take an instance \((G, f, k, v)\) of DRCSM and output the solution from RecApprox\((G, f, k, v, k^{\frac{1}{d}})\). We give the performance guarantees of RecApprox-\(d\) in Theorem 6.

4.1 Overview of RecApprox↩︎

RecApprox takes as input a directed graph \(G\), a non-negative monotone submodular function \(f\), a size constraint \(b\geq 1\), a root vertex \(v\), and a size divisor \(q> 1\). We define the recursion level of a call to RecApprox to be the integer \(\ell\) satisfying \(q^{\ell-1} < b\leq q^{\ell}\). RecApprox outputs an out-tree \(S\subseteq G\), with root \(v\), that \(( \frac{1}{\ell+1}, 1 + 3\ell q+ \ell\log_{3/2} ( \frac{b}{q} ) )\)-approximates \(T^{*}\).

In the base case where \(b= 1\), RecApprox simply returns an out-tree \(S\) consisting of the root, \(v\), and an out-neighbor, \(\hat{w}\), with maximum value.

To give a high-level overview of how RecApprox works in the recursive case where \(b\geq 2\), we first assume \(T^{*}\) can be partitioned into \(\Delta(i)\) out-subtrees whose sizes depend on the \(i\)th iteration of the Line [line:RG32update32loop] loop. That is, \(T^{*}\) can be partitioned into edge-disjoint out-subtrees, \(T^{*}_{i, 1}, \dots, T^{*}_{i, \Delta(i)}\), each of size in the range \([c_{\textrm{min}(i)}, c_{\textrm{max}(i)}]\), where the values of \(c_{\textrm{min}(i)}\) and \(c_{\textrm{max}(i)}\) depend on the \(i\)th iteration. Note that the roots of the out-subtrees \(T^{*}_{i, 1}, \dots, T^{*}_{i, \Delta(i)}\) are all of distance \(b-1\) from \(v\).

RecApprox initializes the output solution, \(S\), with the root, \(v\), and updates it while the remaining number of edges to approximate, \(b_{i}\), is non-zero. Let \(S_{\leq 0} = (\{v\}, \varnothing)\) and, for each iteration \(i\), let \(S_{\leq i}\) be the \(i\)th partial solution, \(\hat{T}_{i}\) be the out-subtree from \(T^{*}_{i, 1}, \dots, T^{*}_{i, \Delta(i)}\) with maximum marginal density to \(S_{\leq i-1}\), \(\hat{w}_{i}\) be the root of \(\hat{T}_{i}\), and \(\hat{c}_{i}\) be the size of \(\hat{T}_{i}\). Then, in the \(i\)th iteration, RecApprox performs these steps: (1) guess \(w_{i} = \hat{w}\) and \(c_{i} = \hat{c}_{i}\), (2) make a recursive call to construct an out-subtree \(S^{w_{i}, c_{i}}_{i}\), with root \(w_{i}\), that is a bicriteria approximation of \(\hat{T}_{i}\), and (3) add \(S^{w_{i}, c_{i}}_{i}\) and a \(v\)–\(w_{i}\) connecting path to \(S_{\leq i-1}\) to get \(S_{\leq i}\).

4.2 Analysis of RecApprox↩︎

We state the performance guarantees of RecApprox in Theorem 4 below. We give a tree partitioning in Lemma 4 and Corollary 6 in order to prove the approximation factor in Lemma 5. The violation factor follows from Lemma 6, and the running time follows from Lemma 7.

Analysis Notation for RecApprox.

We use the following notation throughout the analysis of RecApprox, particularly in the recursive case. The recursion level (of a given RecApprox call) is the integer \(\ell\) satisfying \(q^{\ell-1} < b\leq q^{\ell}\). Let \(t\) denote the total number of updates RecApprox makes in Line [line:RG32update32sol] to construct the output solution. Let \(S_{\leq 0} = ( \{ v\}, \varnothing)\) denote the initial state of the output solution as in Line [line:RG32init32sol], and \(S_{\leq i}\) denote the \(i\)th partial solution as in Line [line:RG32update32sol] of the \(i\)th iteration of the Line [line:RG32update32loop] loop. Further, let \(S^{w_{i}, c_{i}}_{i}\) denote the \(i\)th approximate out-subtree added to the output solution, and \(P_{i}\) denote the path appended to connect \(v\) to \(w_{i}\), i.e., the root of \(S^{w_{i}, c_{i}}_{i}\).

Partitioning the Optimal Solution for RecApprox.

First, for each iteration \(i\) of the Line [line:RG32update32loop] loop, we show that \(T^{*}\) can be partitioned into edge-disjoint out-subtrees each of size in the range \([c_{\textrm{min}(i)}, c_{\textrm{max}(i)}]\), where \(c_{\textrm{min}(i)}= \lceil \frac{1}{3} \max\{ \min\{ \frac{b}{q}, b_{i-1} \}, 1 \} \rceil\) and \(c_{\textrm{max}(i)}= \lfloor \frac{1}{3} \max\{ \min\{ \frac{b}{q}, b_{i-1} \}, 1 \} \rfloor\) as in Lines [line:RG32assign32target32subsize32min] and [line:RG32assign32target32subsize32max]. We use the following tree partitioning lemma based on balanced separators for trees.

We now prove Corollary 6 for partitioning \(T^{*}\).

Approximation Factor of RecApprox.

Violation Factor of RecApprox.

Before bounding the size of the output out-tree in Lemma 6, we bound the number of updates \(t\) to the output out-tree.

Running Time of RecApprox.

4.3 Analysis of RecApprox-\(d\)↩︎

Recall that RecApprox-\(d\) simply takes an instance \((G, f, k, v)\) of DRCSM and outputs the solution from RecApprox\((G, f, k, v, k^{\frac{1}{d}})\). We state the performance guarantees of RecApprox-\(d\) in Theorem 6, which we prove after proving a few simple claims.

We first prove Claim 7, which concerns the recursion level of the initial call to RecApprox. Recall that the recursion level (of a given RecApprox call) is the integer \(\ell\) satisfying \(q^{\ell-1} < b\leq q^{\ell}\). Afterwards, we prove Claims 8 and 9, which are relevant to bounding the size of the tree output by RecApprox.

5 Related Work↩︎

Variants of (Directed Rooted) Connected Submodular Maximization

Kuo et al. [1] introduced the variant of CSM known as Maximum Connected Submodular function with a Budget constraint (MCSB). Here, we are given an undirected graph \(G\) with positive integer vertex costs, a non-negative monotone submodular function \(f\) on the vertices of \(G\), and a budget \(B\). The goal is to select a connected subgraph of \(G\), of cost at most \(B\), whose vertex set maximizes \(f\). Kuo et al. [1] showed a polynomial time \(\Omega(\frac{1}{(\Delta'+1) \sqrt{B}})\)-approximation algorithm for MCSB, where \(\Delta'\) is the maximum degree in \(G\). D’Angelo et al. [25] later improved on this by giving a polynomial time \(\Omega(\frac{1}{\sqrt{B}})\)-approximation algorithm for the directed generalization of MCSB known as Directed Unrooted Submodular Tree (DUST).

Ghuge and Nagarajan [24] introduced the variant of DRCSM known as Submodular Tree Orienteering (STO). Here, we are given a directed graph \(G\) with positive integer edge costs, a non-negative monotone submodular function \(f\), a budget \(B\), and a root vertex \(v\). The goal is to find an out-tree in \(G\), with root \(v\) and cost at most \(B\), whose vertex set maximizes \(f\). Ghuge and Nagarajan showed a quasi-polynomial time \(\Omega(\frac{\log \log k'}{\log k'})\)-approximation algorithm, where \(k'\) is the number of vertices in an optimal tree. This approximation is tight as implied by a known hardness result for Group Steiner Tree (see below).

D’Angelo et al. [25] introduced the variant of DRCSM known as Directed Rooted Submodular Tree (DRST). DRST is defined like STO except that positive integer costs are assigned to vertices rather than edges; in fact, D’Angelo et al. showed an approximation-preserving reduction from STO to DRST. D’Angelo et al. [25] showed, for every \(\delta\in (0, 1]\), a polynomial time \(O(\frac{\delta^{3}}{\sqrt{B}})\)-approximation algorithm that violates the budget by at most a factor of \((1+\delta)\).

Variants of (Directed Rooted) Connected Maximum Coverage

Ran et al. [26] introduced the variant of CMC known as Connected Budgeted maximum Coverage (CBC) (they called this problem Maximum Weight Budgeted Connected Set Cover). Here, we are given a universe of elements \(X\) wherein each element has a non-negative weight, an undirected graph \(G\) where each vertex is a subset of \(X\) and has a non-negative cost, and a budget \(B\). The goal is to select a connected subgraph of \(G\), of cost at most \(B\), whose vertex set maximizes the total weight of its covered elements. Ran et al. studied CBC under the assumption that every pair of subsets (vertices) with a non-empty intersection is adjacent in \(G\), which is a realistic assumption in, e.g., wireless sensor network applications. They gave a polynomial time \(\Omega(\frac{1}{(\Delta'+ 1) \log n})\)-approximation algorithm, where \(\Delta'\) is the maximum degree in \(G\) and \(n\) is the number of vertices in \(G\). D’Angelo et al. [25] later improved the approximation factor to \(\Omega(\frac{1}{\log n})\) under the same assumption. D’Angelo and Delfaraz [27] studied CBC in general; they showed, for every \(\delta\in (0,1]\), a polynomial time \(\Omega(\frac{\delta^2}{\log(n+ |X|) \log |X|})\)-approximation algorithm that violates the budget by at most a factor of \((1 + \delta)\).

D’Angelo and Delfaraz [27] also introduced and studied the variant of DRCMC known as Directed rooted Connected Budgeted maximum Coverage (DCBC). DCBC generalizes CBC by letting \(G\) be a directed graph and by specifying a root vertex \(v\); the goal is to select an out-tree, with root \(v\) and cost at most \(B\), whose vertex set maximizes the total weight of its covered elements. D’Angelo and Delfaraz [27] gave, for every \(\delta\in (0,1]\), a polynomial time \(\Omega(\frac{\delta^2}{\sqrt{n} \log^{2} |X|})\)-approximation algorithm that violates the budget by at most a factor of \((1 + \delta)\). They mentioned that their techniques cannot be directly applied to the generalizations of CBC and DCBC where the objective function is monotone submodular.

We briefly mention that previous works have studied CMC in special geometric settings, achieving polynomial time constant-factor approximations [14], [15]. Also, previous works have studied the special case of CMC known as Budgeted Connected Dominating Set, again achieving polynomial time constant-factor approximations [13], [35], [36]. This problem has application to selecting a limited set of connected and influential users in a social network.

Group Steiner Tree

In Group Steiner Tree (GST), we are given an undirected graph \(G\) with edge costs and a collection of subsets of the vertices, called groups. The goal is to select a minimum cost tree in \(G\) that contains at least one vertex from every group. This problem is polylogarithmic approximable by both polynomial time [37]–[40] and quasi-polynomial time [31], [41] algorithms; in particular Grandoni et al. [31] gave a quasi-polynomial time \(O(\frac{\log^{2} n}{ \log \log n})\)-approximation algorithm and showed a matching hardness result by modifying the hardness result of Halperin and Krauthgamer [29].

GST generalizes Set Cover and is a special case of Directed Steiner Tree (DST). Interestingly, DST has so far appeared to be more challenging than GST for polynomial time algorithms. Charikar et al. [41] gave the current-best polynomial time algorithm for DST, achieving a \(O(\frac{z^{\varepsilon} \log z}{\varepsilon^2})\)-approximation in polynomial time for a constant \(\varepsilon> 0\), where \(z\) is the number of terminal vertices to be covered.

Hardness Results for GST and Budgeted Variants of CSM

For GST, there are known approximation hardness results that apply to quasi-polynomial time algorithms and, thus, to polynomial time algorithms as well. Letting \(n\) be the input size, Halperin and Krauthgamer [29] showed that, for every fixed \(\varepsilon> 0\), a \(O( \log^{2-\varepsilon} n)\)-approximation is not possible in quasi-polynomial time assuming \(\text{NP} \nsubseteq \text{ZPTIME}(n^{\mathop{\mathrm{polylog}}n})\). This result holds even when the input graph is restricted to being a tree, in which case edge and vertex costs are equivalent. Grandoni et al. [31] modified this hardness result to show that a \(o(\frac{\log^{2} n}{ \log \log n})\)-approximation is not possible in quasi-polynomial time assuming the Projection Game Conjecture and \(\text{NP} \nsubseteq \bigcap_{0 < \varepsilon< 1} \text{ZPTIME}( 2^{n^{\varepsilon}} )\). They also show that this is tight by providing a quasi-polynomial time \(O(\frac{\log^{2} n}{ \log \log n})\)-approximation algorithm.

For variants of CSM with edge or vertex costs, there are near-logarithmic approximation hardness results as implied by the above hardness results for GST [29], [31]; we explain these implications below. We explain how the hardness results for GST and the budgeted variant of CSM (with edge costs). Consider a maximization variant of GST, where we are additionally given a budget \(B\), and the goal now is to select a tree in \(G\), of cost at most \(B\), that maximizes the number of groups it covers. This is just a special case of budgeted CSM with edge costs, since the objective function to be maximized is a coverage function. Then, for a value \(\alpha \geq 1\), every \(\frac{1}{\alpha}\)-approximation algorithm for budgeted CSM implies an \((\alpha \ln n)\)-approximation algorithm for GST by a set-covering approach. Thus, the aforementioned hardness results imply that, for budgeted CSM, \(\Omega( \frac{1}{\log^{1-\varepsilon} n} )\) and \(\omega(\frac{\log \log n}{\log n})\)-approximations are not possible in quasi-polynomial time (given the respective hardness assumptions). These hardness results extend to the budgeted variants of (Directed Rooted) CSM mentioned above, including those with vertex costs rather than edge costs. However, they do not carry over easily to CSM (which has uniform costs) since the original hardness results for GST rely on constructing a tree instance with carefully assigned edge costs.

We also mention that, for the vertex-cost variant of CSM, Kortsarz and Nutov [30] showed that, even when allowing the budget to be violated by a universal constant factor, a \(\omega(\frac{1}{\log \log n})\)-approximation is not possible in quasi-polynomial time assuming \(\text{NP} \nsubseteq \text{Quasi}(\text{P})\). In fact, Kortsarz and Nutov proved their hardness result for the special case of the problem where the objective function is additive.

Polymatroid Steiner Tree

In Polymatroid Steiner Tree (PST), we are given an undirected graph \(G\) with edge costs and a non-negative monotone integer-valued submodular function, \(f\), on the vertex set of \(G\). The goal is to select a minimum cost tree \(S\subseteq G\) with \(f(S) = f(V)\), i.e., the vertex set of \(S\) is a base of the polymatroid associated with \(f\). This problem generalizes GST and Covering Steiner Tree.

PST was introduced by Calinescu and Zelikovsky [23], motivated by an application to sensor networks. They gave a polynomial time \(O( \log^{1+\varepsilon} n\log z)\)-approximation algorithm, where \(z= f(V)\), for the case where \(G\) is a tree; this algorithm extends the combinatorial algorithm of Chekuri et al. [40] for GST. For PST on general undirected graphs, a polynomial time \(O( \log^{2+\varepsilon} n\log z)\)-approximation is obtained by taking a tree embedding of the input graph and running the above algorithm on it.

Im et al. showed [22] that the above algorithm implies a bicriteria \((\Omega(1), O(\log^{2+\varepsilon} n))\)-approximation for Submodular Orienteering; the same implication holds for STO on undirected graphs as this is essentially equivalent to Submodular Orienteering. This further implies a polynomial time \(\Omega(\frac{1}{\log^{2+\varepsilon} n})\)-approximation for CSM by selecting a valuable size-\(k\) subtree.

Polymatroid Directed Steiner Tree

In Polymatroid Directed Steiner Tree (PDST), we are given a directed graph \(G\) with edge costs, a non-negative monotone integer-valued submodular function, \(f\), on the vertex set of \(G\), and a root vertex \(v\). The goal is to select a minimum cost out-tree \(S\subseteq G\) with root \(v\) and \(f(S) = f(V)\).

PDST was also introduced by Calinescu and Zelikovsky [23]. They gave, for each integer \(d\geq 2\), a \(d^{3} z^{\frac{1}{d}}\)-approximation algorithm that runs in time \(O(n^{d+1} z^{2d+2})\), where \(z= f(V)\); this algorithm extends the algorithm by Charikar et al. [41] for Directed Steiner Tree. Ghuge and Nagarajan [24] showed that their quasi-polynomial time algorithm for STO implies, by a set-covering approach, a quasi-polynomial time \(O(\frac{\log^2 z}{\log \log z})\)-approximation algorithm for PDST. Recently, Chekuri et al. [42] considered PDST, as well as its special cases, when \(G\) is planar, showing polynomial time polylogarithmic approximation algorithms. Their work builds on ideas from Friggstad and Mousavi [43] for Directed Steiner Tree on planar graphs.

RecApprox-\(d\) Compared to Algorithm for Polymatroid Directed Steiner Tree

Recall that, for each integer \(d\geq 1\), our algorithm RecApprox-\(d\) (Algorithm 2) finds a bicriteria \(( \frac{1}{d+1}, (d+1)^2 k^{\frac{1}{d}} )\)-approximation for DRCSM in time \(O(n^{d+1} k^{2 d+2})\) (Theorem 6) by calling RecApprox with size constraint \(k\), root \(v\), and value \(q= k^{\frac{1}{d}}\). Similarly, for each integer \(d\geq 2\), Calinescu and Zelikovsky’s algorithm finds a \(d^{3} z^{\frac{1}{d}}\)-approximation for PDST in time \(O(n^{d+1} z^{2d+2})\), where \(z= f(V)\). Calinescu and Zelikovsky’s PDST algorithm uses a recursive greedy strategy similar to our algorithm RecApprox. In general, their algorithm takes as input \((f, \ell, z, v, X)\), where \(f\) is the objective function, \(\ell\) is the recursion level, \(z\) is the target value, \(v\) is the root vertex, and \(X\) is a set of already spanned vertices. Their algorithm constructs an out-tree \(S\) by adding cost-efficient out-subtrees (constructed recursively) until \(f(S\mid X) \geq z\). However, the main difference between their algorithm and RecApprox is that, for each solution update, they iterate over guesses, \(z'\), of the marginal gain of a cost-efficient out-subtree (these guesses are passed to the recursive calls as the target values). This is why their algorithm’s running time depends on \(z= f(V)\), which may not be polynomially bounded in \(n\). In RecApprox on the other hand, for each solution update, it iterates over guesses of the size of a valuable out-subtree, which are at most \(k\).

We point out that it is possible to adapt the PDST algorithm to achieve a bicriteria approximation for DRCSM similar to the bicriteria \(( \frac{1}{d+1}, (d+1)^2 k^{\frac{1}{d}} )\)-approximation of RecApprox-\(d\). However, this requires additional steps to ensure that the PDST algorithm runs in polynomial time and so that it returns an out-tree \(S\) with value \(f(S) \geq \Omega(\textrm{OPT})\) and size \(O(k^{\frac{1}{d}}) k\) (for constant \(d\)); this results in an extra polynomial factor in the running time compared to that of RecApprox-\(d\). Below we sketch our approach to achieving a bicriteria approximation for DRCSM using the PDST algorithm, though we omit the details.

Let \((G= (V, E), g, k, v)\) be an instance of DRCSM. We first follow the approach of Chekuri and Pal [44] to scale the objective function \(g\) to give an integer-valued function \(g'\) such that the scaled optimal solution value, \(\textrm{OPT}'\), is polynomially bounded: we guess the most valuable vertex in the (original) optimal solution, \(w^{*}\), and define \(g'(S) = \lfloor \frac{k^2 g(S)}{\varepsilon g(w^{*})} \rfloor\), where \(\varepsilon> 0\) is any constant (the rounding does not guarantee that \(g'\) is submodular, but this only loses a constant-factor in the overall approximation). It follows from subadditivity that the scaled optimal solution value, \(\textrm{OPT}'\), is upper bounded by \(\lfloor \frac{k^2 \textrm{OPT}}{\varepsilon g(w^{*})} \rfloor \leq \lfloor \frac{k^2 \cdot k\cdot g(w^{*})}{\varepsilon g(w^{*})} \rfloor \leq \frac{k^{3}}{\varepsilon}\). Now we follow an approach similar to that in Theorem 3.1 of Im et al. [22] to solve the scaled instance: we guess the scaled optimal value, \(\textrm{OPT}'\), and define the truncated function \(f(S) = \min\{ \textrm{OPT}', g'(S) \}\). Then we run the PDST algorithm with input \((f, d, \textrm{OPT}', v, \varnothing)\) and stop the algorithm once it constructs an out-tree \(S\) satisfying \(f(S) \geq \frac{\textrm{OPT}'}{2}\). Finally, we return \(S\) as the solution to our original instance of DRCSM. Note that, in order to prove that the returned out-tree \(S\) has size \(O(k^{\frac{1}{d}}) k\), we would need to invoke the height reduction lemma (Lemma 1) of Calinescu and Zelikosvsky [23].

6 Conclusions↩︎

We presented a novel polynomial time framework that, for (Directed) CSM, achieves a \(\Omega(\frac{\varepsilon^{3}}{{r}^{\varepsilon}})\)-approximation for every constant \(\varepsilon \in (0, 1]\); and, for DRCSM, achieves a bicriteria \((\Omega(\frac{\delta \varepsilon^{3}}{{r}^{\varepsilon}}), 1 + \delta)\)-approximation for every \(\delta \in [\frac{1}{k}, 1]\) and constant \(\varepsilon \in (0, 1]\). This outperforms the state of the art with respect to the size constraint, \(k\), and the optimal solution radius, \(r\). As part of our framework, we proposed the algorithms GreedyRadius and RecApprox-\(d\) for Directed Rooted CSM. GreedyRadius takes a bicriteria \((\alpha(k), \beta(k))\)-approximation subroutine and uses it to construct a \((\Omega(\alpha(r)), O(\beta(r)))\)-approximate solution. RecApprox-\(d\) can be used as this subroutine, giving a bicriteria \((\frac{1}{d+1}, (d+1)^2 k^{\frac{1}{d}})\)-approximation in time \(O(n^{d+1} k^{2d+2})\).

A potential future direction is to extend our framework to problems with edge or vertex costs, such as Submodular Tree Orienteering (edge costs) or Directed Rooted Submodular Tree (vertex costs). Further, for rooted network design problems such as DRCSM and the aforementioned problems, it is an open problem to show a polynomial time \(\Omega(\frac{1}{k^{\varepsilon}})\) or \(\Omega(\frac{1}{r^{\varepsilon}})\)-approximation algorithm that does not violate the size or budget constraint. Lastly, it would be interesting to prove a stronger approximation hardness result for CSM than the one already implied by the cardinality constrained problem, as this could inform us on whether our algorithms achieve tight approximation factors with respect to \(k\). If so, this would further motivate algorithms with beyond-worst-case guarantees.

References↩︎

---

1. Our formulation of CSM is equivalent to the formulation where the goal is to select a set \(S' \subseteq V\), of \(k'\) vertices that are connected in \(G\), that maximizes \(f\). This is because \(S'\) must have a spanning tree with \(k'-1 = k\) edges.↩︎