---
abstract: |
    In [Source Location]{} ([SL]{}) problems the goal is to select a minimum cost source set $S$ such that the connectivity from $S$ to any node $v$ is at least the demand $d_v$ of $v$. In [Network Augmentation]{} ([NA]{}) problems we are given a graph $G=(V,E)$ and an edge-set $F$ on $V$, edge-costs on $F$ or node-costs on $V$, and connectivity requirements $\{r_{sv}:sv \in D\}$ on a set $D$ of “demand edges”. The goal is to compute a minimum cost edge-set $I \subseteq F$, such that in the graph $G+I$, the connectivity of each $sv \in D$ is at least $r_{sv}$. In [Rooted NA]{} $D$ is a star with center $s$, and in [$a$-Based NA]{} $F$ is a star with center $a$. We suggest a notion of $q$-connectivity, where every node $u$ has capacity $q_u \geq 1$ that represents the resistance of $u$ to failures. We observe that a large class of [SL]{} problems, including the variants that appear in the literature, is a particular case of $q$-connectivity [$s$-Based Rooted NA]{} problems. We use this to derive some approximation algorithms for [SL]{} from those for [NA]{}, as well as to derive some new results for [SL]{} problems. Some of our results are as follows.

    -   We observe that directed [SL]{} with unit costs is $\Omega(\log n)$-hard to approximate even with $0,1$ demands, while some versions of [SL]{} with uniform demands can be solved in polynomial time.

    -   We show that the $H(|D|)$-approximation algorithm of [@KN-aug] for edge costs [$a$-Based NA]{} has ratio $H(\alpha)$ for the $q$-connectivity version with node-costs, where $p_{\max}$ is the maximum number of parallel edges in $F$, $\alpha=\min\{r(D),|D| \cdot p_{\max}\}$, and $H(j)=\sum_{i=1}^j 1/i$ is the $j$th harmonic number. This gives a simple unifying $H(d(V))$-approximation algorithm for several [SL]{} variants considered separately by Sakashita, Makino, and Fujishige [@SMF]. Moreover, we will show that this is so whenever the connectivity function is submodular.

    -   For undirected [$a$-Based NA]{} we give an approximation algorithm with ratio $\min\{k,p_{\max} \ln k\} \cdot O(\ln k)$ for node-costs and $O(\ln^2 k)$ for edge-costs, where $k=\max_{v \in V}d_v$ is the maximum demand; the latter improves the ratio $\tilde{O}(k)$ of Fukunaga [@Fuk].

    -   We consider a variant of [SL]{} where we also have edge-costs and flow-cost bounds $\{b_v: v \in V\}$, and require that for every node $v$, the minimum cost of a flow of value $d_v$ from $S$ to $v$ is at most $b_v$. We show that the problem admits approximation ratio $H(d(V))+H(c(E))$.

author:
- Guy Kortsarz
- Zeev Nutov
title: |
    A unified approach to source location\
    via rooted network augmentation
---

Introduction
============

Problems considered and relations between them
----------------------------------------------

In this paper we suggest a unifying approach to handle [Source Location]{} problems via [Rooted Network Augmentation]{} problems. In [Source Location]{} problems the goal is to select a minimum cost source set $S$ such that the connectivity from $S$ to any other node $v$ is at least the demand $d_v$ of $v$. In [Network Augmentation]{} problems the goal is to augment a given graph by a minimum-cost edge-set such that the new graph satisfies prescribed connectivity requirements. Formally, the generic versions of these problems are as follows. Given a function $w=\{w_u:u \in U\}$ on a groundset $U$ and $U' \subseteq U$, let $w(U')=\sum_{u \in U'}w_u$. If $w$ is a cost function on $U$ and $I$ is an edge-set on $U$, then the cost (or the node-costs) $w(I)$ of $I$ is defined to be the cost of the set of the endnodes of $I$. Also, let $w_{\max}=\max_{u \in U} w_u$ denote the maximum value of $w$, and assume that all the input numbers are integers.

In [NA]{} problems, typical connectivity functions are as follows.

-   [*Edge-connectivity $\lambda_G(s,v)$*]{} is the maximum number of pairwise edge disjoint $sv$-paths in $G$.

-   [*Node-connectivity $\kappa_G(s,v)$*]{} is the maximum number of pairwise internally disjoint $sv$-paths in $G$.

-   [*$Q$-connectivity $\lambda_G^Q(s,v)$*]{} for given $Q \subseteq V$, is the maximum number of $sv$ paths no two of which have an edge or an internal node in $Q$ in common. Note that $Q$-connectivity reduces to edge-connectivity if $Q=\emptyset$, and to node-connectivity if $Q=V$; namely, $\lambda_G^\emptyset(s,v)=\lambda_G(s,v)$ and $\lambda_G^V(s,v)=\kappa_G(s,v)$.

The corresponding versions of [NA]{} are edge-connectivity [NA]{} when $f_{sv}(I)=\lambda_{G+I}(s,v)$, node-connectivity [NA]{} when $f_{sv}(I)=\kappa_{G+I}(s,v)$, and $Q$-connectivity [NA]{} when $f_{sv}(I)=\lambda^Q_{G+I}(s,v)$.

Most papers that considered [SL]{} problems defined $(S,v)$-edge-connectivity $\lambda_G(S,v)$ as the maximum number of pairwise edge-disjoint $(S,v)$-paths. On the other hand, several definitions were used for $(S,v)$-node-connectivity $\kappa(S,v)$; in most of these definitions, $\kappa(S,v)=\infty$ if $v \in S$. Here we suggest a definition that captures previous definitions as particular cases.

Note that $\lambda_G^Q(s,v)$ is the maximum $sv$-flow value, where edges and nodes in $Q$ have unit capacities, while the capacity of the nodes in $V \setminus Q$ is $\infty$. Hence the $Q$-connectivity function $\lambda_G^Q(s,v)$ is the max-flow/min-cut value function in $G$ with node-capacities in $\{1,\infty\}$ and unit edge capacities. In Definition \[d:pq\] below, this is generalized as follows. Every node $u$ has capacity $q_u$ (the resistance of $u$ to failures), and an amount $p_u$ of flow-supply that $u$ can deliver to any other node (including itself) if $u$ is chosen to be in the source set $S$.

\[d:pq\] Let $G=(V,E)$ be a graph with node-capacities $\{q_u:u \in V\}$. For $S \subseteq V$ and $v \in V$ the $(S,v)$-$q$-connectivity $\lambda_G^q(S,v)$ is the maximum flow value from $S \setminus \{v\}$ to $v$ (every edge has capacity $1$). Equivalently, $\lambda_G^q(S,v)$ is the minimum capacity of a cut $C \subseteq E \cup V \setminus \{v\}$ such that $G \setminus C$ has no $(S,v)$-path. Given [*flow-supplies*]{} $\{p_u:u \in S\}$, the $(S,v)$-$(p,q)$-connectivity $\lambda_G^{p,q}(S,v)$ is the maximum $(s,v)$-flow value $\lambda_{G'}^q(s,v)$ in the network $G'$ obtained by adding to $G$ a new node $s$ and connecting it to every $u \in S$ with $p_u$ edges; hence if $p_u \geq q_u$ for every $u \in S$ then: $\lambda_G^{p,q}(S,v)=p_v+\lambda_G^q(S,v)$ if $v \in S$, and $\lambda_G^{p,q}(S,v)=\lambda_G^q(S,v)$ otherwise.

Note that $\lambda_G(S,v)=\lambda_G^{p,q}(S,v)$ for $p_u= \infty$ and $q_u=\infty$ for every $u \in V$, and that $\lambda_G^Q(s,v)=\lambda_G^q(s,v)$ for $q_u=1$ if $u \in Q \setminus \{s,v\}$ and $q_u=\infty$ otherwise. Now we mention some node-connectivity functions $\psi$ that appear in the literature, and show that they are particular case of the $(p,q)$-connectivity function $\lambda_G^{p,q}$ with $p_u,q_u \in \{1,\infty\}$ and $q_u \leq p_u$.

1.  $\kappa(S,v)$ is the maximum number of $(S,v)$-paths no two of which have a common node in $V \setminus (S \cup v)$ if $v \notin S$, and $\kappa(S,v)=\infty$ otherwise; equivalently, $\kappa(S,v)$ is the minimum size $|C|$ of a cut $C \subseteq E \cup V \setminus (S \cup \{v\})$ such that $G \setminus C$ has no $(S,v)$-path.\
    For directed graphs, [$\kappa$-SL]{} is equivalent to [$\lambda$-SL]{} by the following (approximation ratio preserving) standard reduction: replace every $v \in V$ by two nodes $v^{in}, v^{out}$ connected by an edge $v^{in}v^{out}$, and replace every edge $uv \in E$ by an edge $u^{out}v^{in}$; each node $v^{out}$ inherits the cost and the demand of $v$, while $v^{in}$ has cost $\infty$ and demand $0$. It is not hard to verify that $S$ is a feasible solution to the original instance with connectivity function $\kappa$ if, and only if, $S^{out}=\{v^{out}:v \in S\}$ is a feasible solution to the obtained instance with the edge-connectivity function $\lambda$. For undirected graphs, we do not see that $\kappa$ is a particular case of $\lambda_G^{p,q}$, but we are also not aware on any work on [*undirected*]{} [$\kappa$-SL]{} (except that it is shown in [@III] that the problem can be solved in polynomial time for $k=\max_{v \in V} d_v \leq 2$ and is NP-hard for $k \geq 3$).

2.  $\hat{\kappa}(S,v)$ is the maximum number of $(S,v)$-paths no two of which have a common node in $V \setminus \{v\}$ if $v \notin S$, and $\hat{\kappa}(S,v)= \infty$ otherwise; equivalently, $\hat{\kappa}(S,v)$ is the minimum size $|C|$ of a cut $C \subseteq E \cup V \setminus (\{v\})$ such that $G \setminus C$ has no $(S,v)$-path.\
    Then $\hat{\kappa}(S,v)=\lambda_G^{p,q}(S,v)$ for $p_u=\infty$ and $q_u=1$ for every $u \in V$.

3.  $\kappa'(S,v)=\hat{\kappa}(S,v)$ if $v \notin S$ and $\kappa'(S,v)=1+ \hat{\kappa}(S \setminus \{v\},v)$ if $v \in S$; equivalently, $\kappa'(S,v)$ is the minimum size $|C|$ of a cut $C \subseteq E \cup V \setminus (\{v\})$ such that $G \setminus C$ has no $(S \setminus \{v\},v)$-path.\
    Then $\kappa'(S,v)=\lambda_G^{p,q}(S,v)$ for $p_u=1$ and $q_u=1$ for every $u \in V$.

Given an instance of [SL]{} or of [NA]{}, let $k$ denote the maximum demand $d_{\max}=\max_{v \in V} d_v$ or the maximum requirement $r_{\max}=\max_{uv \in D}r_{uv}$. Note that in [SL]{} problems with $\psi(S,v)=\lambda_G^{p,q}(S,v)$, we may always assume that $p_u \leq k$, and it is also reasonable to assume that $1 \leq q_u \leq p_u$ for every $u \in V$ (as in the above versions). We consider a relation between such $(p,q)$-connectivity versions of [SL]{} and $q$-connectivity versions of [NA]{}, that formally are defined as follows.

Now we define several particular important cases of [NA]{}.

The [$a$-Based Connectivity Augmentation]{} problem was defined in [@KN-aug], where it was also shown to admit an $H(r(D))$-approximation algorithm. The study of this problem in [@KN-aug] is motivated by the following observation.

\[[@KN-aug]\] \[o:aug\] If directed [$a$-Based Connectivity Augmentation]{} admits approximation ratio $\rho$, then directed [Connectivity Augmentation]{} admits the following approximation ratios: $2\rho$ if $Q \neq V$, and $2k \rho$ if $Q=V$.

For an edge-set/graph $J$ let $\delta_J(X)$ denote the set of edges in $J$ from $X$ to $V \setminus X$. This paper is motivated by a recent paper of Fukunaga [@Fuk], that defined the connectivity function $\kappa'$, and observed that [$\kappa'$-SSL]{} is equivalent to the particular case of [$s$-Based Rooted SNA]{} with node-connectivity requirements and [*edge-costs*]{}, and with $\delta_G(s)=\emptyset$. Here, by the same reduction as in Definition \[d:pq\] (for a proof see Section \[s:hard\]), we further observe the following.

\[o:reduction\] For both directed and undirected graphs, [SSL]{} is equivalent to [$s$-Based Rooted SNA]{} with node-costs and with $\delta_G(s)=\emptyset$ and $c(s)=0$.

We also consider the following generalization of [SSL]{}. Given an instance of [SSL]{} and edge-costs $\{c_e:e \in E\}$ let $\mu_G(S,v)$ denote the minimum cost of an edge set $F \subseteq E$ such that $\lambda^{p,q}_{(V,F)}(S,v) \geq d_v$, where $\mu_G(S,v)=\infty$ if no such edge set $F$ exists (namely, if $\lambda^{p,q}_G(S,v) < d_v$).

Previous work
-------------

The previously best known approximation ratios and hardness of approximation results for [SL]{} problems with connectivity functions $\lambda,\kappa,\hat{\kappa},\kappa'$, are summarized in Table 1; see also a survey in [@NI].

\[tbl:ratios\]

  [ $c$  &  $d$]{}                                                                                                         
  ------------------ --------------------------------- --------------------------------- --------------------------------- ---------------------------------
                     [*Undirected*]{}                  [*Directed*]{}                    [*Undirected*]{}                  [*Directed*]{}
  GC & GD            $\Theta(\ln d(V))$ [@BKP; @SMF]   $\Theta(\ln d(V))$ [@BKP; @SMF]   $\Theta(\ln d(V))$ [@BKP; @SMF]   $\Theta(\ln d(V))$ [@BKP; @SMF]
  GC & UD            in P [@AIMF]                      $O(\ln d(V))$ [@BKP]              $O(\ln d(V))$ [@BKP]              $O(\ln d(V))$ [@BKP]
  UC & GD            in P [@AIMF]                      $O(\ln d(V))$ [@BKP]              $O(\ln d(V))$ [@BKP]              $O(\ln d(V))$ [@BKP]
  UC & UD            in P [@TSSA]                      in P [@IMAH]                      $O(\ln d(V))$ [@BKP]              $O(\ln d(V))$ [@BKP]
                                                                                                                           
  GC & GD            $\Theta(\ln d(V))$ [@SMF]         $\Theta(\ln d(V))$ [@SMF]         $O(\ln d(V))$ [@Fuk]              $O(\ln d(V))$ [@Fuk]
                     $O(k \ln k)$ [@Fuk]                                                 $O(k \ln k)$ [@Fuk]               
  GC & UD            in P [@NII]                       in P [@NII]                                                         
  UC & GD            $O(\ln d(V))$ [@SMF]              $O(\ln d(V))$ [@SMF]              $O(\ln d(V))$ [@Fuk]              $O(\ln d(V))$ [@Fuk]
                     $O(k)$ [@Ishii]                                                                                       
  UC & UD            in P [@NII]                       in P [@NII]                                                         

  :  Previous approximation ratios and hardness of approximation thresholds for [SL]{} problems. GC and UC stand for general and uniform costs, GD and UD stand for general and uniform demands, respectively.

Some additional results are as follows. Ishii, Fujita, and Nagamochi [@IFN2; @IFN] showed that undirected [SSL]{} with $\hat{\kappa}$ can be solved in polynomial time for $k \leq 3$, but is NP-hard if there exists a vertex $v \in V$ with $d(v) \geq 4$. Barasz, Becker, and Frank [@BBF] gave a strongly polynomial time algorithm for edge-connectivity directed [SSL]{} with uniform demands. Several generalizations of source location problems can be found in [@SMNF; @IM; @MUMF; @III].

Our results
-----------

Our first result is an easy consequence from Observation \[o:reduction\], and it illustrates the usefulness of the relation between the two problems.

\[t:hard\] Directed [SSL]{} for $k=1$ and unit costs is $\Omega(\log n)$-hard to approximate. Directed/undirected [$\kappa'$-SSL]{} with uniform demands can be solved in polynomial time.

Observations \[o:aug\] and \[o:reduction\] motivate the study of the [$a$-Based SNA]{} problem. Interestingly, the algorithms of [@SMF] for [SL]{} with connectivity functions $\lambda$,$\kappa,\hat{\kappa}$, and the algorithm of [@KN-aug] for [$a$-Based Connectivity Augmentation]{} both use the same method of reducing the problem to a [Submodular Cover]{} problem. Now we see that this is not a coincidence, since by Observations \[o:aug\] and \[o:reduction\], both problems are particular cases of the [$a$-Based SNA]{} problem. Furthermore, we will show by a simple proof that such a reduction is possible whenever the connectivity function is submodular and non-decreasing. A set function $f$ on $U$ is submodular if $f(X)+f(Y) \geq f(X \cap Y)+f(X \cup Y)$ for all $X,Y \subseteq U$, and $f$ is non-decreasing if $f(X) \leq f(Y)$ for all $X \subseteq Y \subseteq U$. Our next result is obtained by observing that the algorithm of [@KN-aug] for [$a$-Based Connectivity Augmentation]{} extends to [$a$-Based NA]{} with arbitrary submodular non-decreasing connectivity function, for both edge-costs and node-costs, as follows. Recall that for an [$a$-Based SNA]{} instance, $p_{\max}$ denotes the maximum number of parallel edges in $F$, and that $p_{\max} \leq k$.

\[t:aug\] If for a directed [$a$-Based SNA]{} instance each function $f_{uv}(I)$ is submodular and non-decreasing, then the problem admits an approximation algorithm with ratio $H(\alpha)$, where $\alpha = \max\limits_{e \in F} \sum_{uv \in D} [f_{uv}(\{e\})-f_{uv}(\emptyset)]$ in the case of edge costs, and $\alpha = \max\limits_{z \in V} \sum_{uv \in D}[f_{uv}(\delta_F(z))-f_{uv}(\emptyset)]$ in the case of node costs.

In Section \[s:a\] we observe that for [$a$-Based SNA]{} instances, the set-function on $F$ defined by $f_{uv}(I)=\lambda^q_{G+I}(u,v)$ is submodular and non-decreasing, and that $\alpha \leq |D|$ in the case of edge-costs and $\alpha \leq \min\{r(D),|D| \cdot p_{\max}\}$ in the case of node-costs, where $p_{\max}$ is the maximum number of parallel edges in $F$.

\[t:a\] Directed [$a$-Based SNA]{} admits approximation ratios $H(|D|)$ for edge-costs and $H(\min\{r(D),|D| \cdot p_{\max}\})$ for node-costs. Thus directed [SSL]{} admits approximation ratio $H(\min\{r(D),|D| \cdot p_{\max}\})$.

For both [SSL]{} and [SNA]{}, an approximation ratio $\rho$ for directed graphs implies approximation ratio $2\rho$ for undirected graphs. Usually, undirected connectivity problems are easier to approximate than the directed ones. Directed [SSL]{} is already [Set-Cover]{} hard even for $k=1$ and unit costs, but for undirected [SSL]{} with $k=1$ (and even with $k=2$) it is not hard to obtain a polynomial time algorithm. Hence a natural question is whether undirected [SSL]{} admits an approximation ratio that depends on $k$ only. As was mentioned, Fukunaga [@Fuk] observed that $Q$-connectivity [SSL]{} with $Q=V$ is equivalent to [$s$-Based Rooted SNA]{} with edge-costs. Since undirected $Q$-connectivity [Rooted SNA]{} with edge-costs admits ratio $O(k\ln k)$ [@N-focs], so is $Q$-connectivity [SSL]{} with $Q=V$. However, [Connectivity Augmentation]{} admits ratio $O(\ln^2k)$ for rooted requirements [@N-aug], and a natural question to ask is whether the algorithm of [@N-aug] extends to [$s$-Based Rooted SNA]{}.

\[t:main’\] Undirected [$a$-Based SNA]{} admits the following approximation ratios, where $H(k)=\sum_{i=1}^k 1/i$ denotes the $k$th Harmonic number.

-   For edge-costs, $\sum_{\ell=1}^k \frac{H(\Delta_\ell)}{k-\ell+1} \leq H(k) \cdot H(\Delta_k)=O(\ln^2k)$, where $\Delta_\ell={(4\ell-3)}^2$; [$s$-Based Rooted SNA]{} admits ratio $\sum_{\ell=1}^k \frac{H(2\ell-1)}{k-\ell+1} \leq H(k) \cdot H(2k-1)$.

-   For node-costs, $\sum_{\ell=1}^k H(\Delta_\ell) \min\left\{\frac{p_{\max}}{k-\ell+1},1\right\} \leq
    \min\{k,p_{\max} H(k)\} \cdot H(\Delta_k)$; [$s$-Based Rooted SNA]{}, and thus also undirected [SSL]{}, admits ratio\
    $\sum_{\ell=1}^k H(2\ell-1) \min\left\{\frac{p_{\max}}{k-\ell+1},1\right\} \leq 
    \min\{k,p_{\max} \cdot H(k)\} \cdot H(2k-1)$.

Part (ii) implies that undirected [SSL]{} admits approximation ratio that depends on $k$ only; this ratio is better than the one implied by Theorem \[t:a\] for $k=o\left(\frac{\ln n}{\ln \ln n}\right)$. Furthermore, it improves the ratio $O(k \ln k)$ of Fukunaga [@Fuk] for $\kappa'$-[SSL]{} to $O(\ln^2 k)$, since we have $p_{\max}=1$ in this case (for $\hat{\kappa}$-[SSL]{} we get the same ratio $O(k \ln k)$ as in [@Fuk], since $p_{\max}=k$ in this case).

Finally, we consider the [SSL with Flow-Cost Bounds]{} problem.

\[t:fc-bounds\] [SSL with Flow-Cost Bounds]{} admits approximation ratio $H(d(V))+H(c(E))$.

Theorems \[t:hard\], \[t:aug\], \[t:a\], \[t:main’\], and \[t:fc-bounds\], are proved in Sections \[s:hard\], \[s:aug\], \[s:a\], \[s:main’\], and \[s:fc-bounds\], respectively.

Proof of Theorem \[t:hard\] {#s:hard}
===========================

We start by proving Observation \[o:reduction\]. The reduction is essentially the one in Definition \[d:pq\]. Given an instance of [SSL]{} construct an instance of [$s$-Based Rooted SNA]{} as follows: add to $G$ a new node $s$ of cost $0$, and for every $v \in V$ set $r_{sv}=d_v$ and put $p_v$ edges from $s$ to $v$ into $F$. Conversely, given an instance of [$s$-Based Rooted SNA]{} with node-costs and with $\delta_G(s)=\emptyset$ and $c(s)=0$, construct an instance of [SSL]{} as follows. Remove $s$ from $G$, and for every $v \in V$ set $p_v$ to be the number of edges in $F$ from $s$ to $v$ and $d_v=r_{sv}$. In both directions, it is not hard to see that $S$ is a solution to the [SSL]{} instance, if, and only if, the edge set $I$ of all edges in $F$ from $s$ to $S$ is a solution to the [$s$-Based Rooted SNA]{} instance, and clearly $I$ and $S$ have the same node-cost.

Note that in the above reduction, we have the following.

-   The case of uniform demands (namely, $d_v=k$ for all $v \in V$) in [SSL]{} corresponds to the case of rooted uniform requirements (namely $r_{sv}=k$ for all $v \in V \setminus \{s\}$) in [$s$-Based Rooted SNA]{}.

-   The case of unit costs (namely, $c_v=1$ for all $v \in V$) in [SSL]{} corresponds to the version of [$s$-Based Connectivity Augmentation]{} with node-costs, when we can pick $p_v$ edges from $s$ to $v$ by a cost of $1$.

Directed [Rooted SNA]{} with edge-costs and uniform requirements $r_{sv}=k$ for all $v \in V$ can be solved in polynomial time [@FT]; this easily implies that also undirected [Rooted $s$-Based SNA]{} with edge-costs can be solved in polynomial time. Thus the same holds for [$\kappa'$-SSL]{}, since [$\kappa'$-SSL]{} is a particular case of [$s$-Based Rooted SNA]{} with edge-costs.

Frank [@Frank] showed that [*directed*]{} [$s$-Based Connectivity Augmentation]{} with $\delta_G(s)=\emptyset$ is NP-hard. Using a slight modification of his reduction we can show that the problem is in fact [Set-Cover]{} hard to approximate, and thus is $\Omega(\log n)$-hard to approximate. Given an instance of [Set-Cover]{}, where a family $A$ of sets needs to cover a set $B$ of elements, construct the corresponding directed bipartite graph $G'=(A \cup B,E')$, by putting an edge from every set to each element it contains. The graph $G=(V,E)$ is obtained from $G'$ by adding $M$ copies of $B$, connecting $A$ to each copy in the same way as to $B$, and adding a new node $s$. Let $F=\{sv:v \in V\}$, $c(e)=1$ for every $e \in F$, and $r_{sv}=0$ if $v \in A$ and $r_{sv}=1$ otherwise. It is easy to see that if $I \subseteq F$ is a feasible solution to the obtained [Rooted $s$-Based SNA]{} instance, then either $I$ corresponds to a feasible solution to the [Set-Cover]{} instance, or $|I| \geq M$. The $\Omega(\log n)$-hardness follows for $M$ large enough, say $|M|={(|A|+|B|)}^2$, and $|A|=|B|$. Since for $k=1$ all connectivity functions of [SSL]{} are equivalent, we get $\Omega(\log n)$ hardness for directed [SSL]{} with $k=1$ and unit costs.

Proof of Theorem \[t:aug\] {#s:aug}
==========================

We use a result due to Wolsey [@W] about a performance of a greedy algorithm for submodular covering problems. A generic covering problem is as follows.

The [Submodular Cover]{} problem is a special case when the function $g$ is submodular and non-decreasing, and $c(S)=\sum_{v \in S} c(v)$ for some $c:U\rightarrow \mathbb{R}^+$. Wolsey [@W] proved that then, the greedy algorithm, that as long as $g(A)<g(U)$ repeatedely adds to $A$ an element $u \in U \setminus A$ with maximum $\frac{g(A \cup \{u\})-g(A)}{c_u}$, has approximation ratio $H\left(\max_{u \in U} g(\{u\})-g(\emptyset)\right)$.

We start with the case of edge-costs. Then the function $g$ is defined in the same way as in [@KN-aug]: $U=F$ and for $I \subseteq F$ $$g(I)=\sum_{uv \in D}\min\{r(u,v),f_{uv}(I)\}  .$$ It is not hard to verify that $g$ is non-decreasing, and that $I$ is a feasible solution to an [NA]{} instance if and only if $g(I)=g(F)=r(D)$. Also, $g(\{e\}) - g(\emptyset) \leq \sum_{uv \in D} [f_{uv}(\{e\}) - f_{uv}(\emptyset)]$ for any $e \in F$. We show that $g$ is submodular. It is known (c.f. [@Sch]) that if $h$ is submodular, then $\min\{r,h\}$ is submodular for any constant $r$. Thus the function $h_{uv}(I)=\min\{r(u,v),f_{uv}(I)\}$ is submodular. As a sum of submodular functions is also submodular, we obtain that $g$ is submodular.

Now let us consider node-costs. For $S \subseteq V$ let $F_S$ denote the set of edges in $F$ from $a$ to $S$, and let $f'_{uv}(S)=f_{uv}(F_S)$. We have $U=V$ and for $S \subseteq V$ let $$g'(S)= \sum_{uv \in D}\min\{r(u,v),f'_{uv}(S)\} \ .$$ As in edge-costs case, it is not hard to verify that $g'$ is non-decreasing and that $S$ is a feasible solution to an [NA]{} instance if and only if $g'(S)=g'(V)=r(D)$. Also, $g'(\{z\}) - g'(\emptyset) \leq \sum_{uv \in D} [f_{uv}(\delta_F(z)) - f_{uv}(\emptyset)]$ for any $z \in V$. We show that $g'$ is submodular. We claim that the submodularity of $f(I)$ implies that $f'(S)$ is submodular. This is not true in general, but holds if $F$ is a star, and hence for [$a$-Based NA]{} instances. More precisely, it is not hard to verify the following statement, that finishes the proof of Theorem \[t:aug\].

\[l:star\] Let $(V,F)$ be a graph and let $f$ be a submodular set function on $F$. If $F$ is a star, then the set function $f'(S)=f(F_S)$ defined on $V$ is also submodular.

Proof of Theorem \[t:a\] {#s:a}
========================

All graphs in this section are assumed to be directed. Theorem \[t:a\] will follow from Theorem \[t:aug\] and the following Lemma, whose parts were implicitly proved in [@KN-aug].

\[l:max\] For any directed [$a$-Based SNA]{} instance, for any $s,v \in V$, the set-function $f_{sv}(I)=\lambda^q_{G+I}(s,v)$ on $F$ is submodular and non-decreasing. Furthermore, $f_{sv}(\{e\}) \leq  f_{sv}(\emptyset)+1$ for any $e \in F$, and $f'_{sv}(\{z\})-f'_{sv}(\emptyset) \leq |\delta_F(z)| \leq p_{\max}$ for any $z \in V$.

In the rest of this section we prove Lemma \[l:max\]. Let $s,v \in V$. It is easy to see that $f(I)=f_{sv}(I)=\lambda^q_{G+I}(s,v)$ is non-decreasing, and that the second statement in the lemma holds. Thus it remains to prove that $f(I)$ is submodular. For that, we will use the following known characterization of submodularity, c.f. [@Sch]:\
[*A set-function $f$ on $F$ is submodular if, and only if*]{} $$f(I_0 \cup \{e\})+f(I_0 \cup \{e'\}) \geq f(I_0)+f(I_0 \cup \{e,e'\})  \ \ \ \forall I_0 \subset F, e,e' \in F \setminus I_0 $$ Let us fix $I_0 \subseteq F$. Revising our notation to $G \gets G+I_0$, $F \gets F \setminus I_0$, and denoting $h(I)=f(I_0 \cup I)-f(I_0)$, we get that $f$ is submodular if, and only if $$h(\{e\})+h(\{e'\}) \geq h(\{e,e'\})  \ \ \ \forall e,e' \in F  \ .$$ In our setting, $h(I)=\lambda^q_{G+I}(s,v)-\lambda^q_G(s,v)$ is the increase in the $(s,v)$-$q$-connectivity as a result of adding $I$ to $G$. Thus $0 \leq h(I) \leq |I|$ for any $I \subseteq F$, so $0 \leq h(\{e,e'\}) \leq 2$. If $h(\{e,e'\})=0$, then we are done; if $h(\{e,e'\})=1$, then we need to show that $h(\{e\})=1$ or $h(\{e'\})=1$; and if $h(\{e,e'\})=2$, then we need to show that $h(\{e\})=1$ and $h(\{e'\})=1$. We prove the following general statement, that implies the above.

\[l:J\] Let $G=(V,E)$ be a directed graph with node capacities $\{q_v:v \in V\}$, let $I$ be a set of edges on $V$ disjoint to $E$, let $s,t \in V$, and let $h=\lambda^q_{G+I}(s,t)-\lambda^q_G(s,t)$. Then there is $J \subseteq I$ of size $|J| \geq h$ such that $\lambda^q_{G+\{e\}}(s,t)=\lambda^q_G(s,t)+1$ for every $e \in J$.

Since we consider directed graphs, it is sufficient to prove the lemma for the case of edge-connectivity. For that, apply the following standard reduction that eliminates node capacities: replace every $v \in V \setminus \{s,t\}$ by two nodes $v^{in}, v^{out}$ connected by $q_v$ parallel edges from $v^{in}$ to $v^{out}$ and replace every $uv \in E \cup F$ by an edge from $u^{out}$ to $v^{in}$. Hence we will prove the lemma for the edge connectivity function $\lambda$. Let us say that $S \subseteq V$ is [*tight*]{} if $s \in S$, $v \notin S$, and $|\delta_G(S)|=\lambda_G(s,v)$. Let ${\cal F}$ be the family of tight sets. By Menger’s Theorem ${\cal F}$ is non-empty. It is known that ${\cal F}$ is a ring family, namely, the intersection of all the sets in ${\cal F}$ is nonempty, and if $X,Y \in {\cal F}$ then $X \cap Y, X \cup Y \in {\cal F}$. Then ${\cal F}$ has a unique inclusion-minimal set $S_{\min}$ and a unique inclusion-maximal set $S_{\max}$. Let $J=\{uv \in I:u \in S_{\min},v \in V \setminus S_{\max}\}$ be the set of edges in $I$ that go from $S_{\min}$ to $V \setminus S_{\max}$. By Menger’s Theorem, $|J| \geq h$, and $\lambda_{G+\{e\}}(s,t)=\lambda_G(s,t)+1$ for any $e \in J$. The statement follows.

Proof of Theorem \[t:main’\] {#s:main'}
============================

Here we prove Theorem \[t:main’\]. All graphs in this and the next section are assumed to be undirected, unless stated otherwise. We start by considering the edge-costs case, and then will show that it implies the node-costs case by reductions.

An ordered pair $\hat{X}=(X,X^+)$ of subsets of a groundset $V$ is called a [*biset*]{} if $X \subseteq X^+$; $X$ is the [*inner part*]{} and $X^+$ is the [*outer part*]{} of $\hat{X}$, and $\Gamma(\hat{X})=X^+ \setminus X$ is the [*boundary*]{} of $\hat{X}$. An edge $e$ covers a biset $\hat{X}$ if it has one endnode in $X$ and the other in $V \setminus X^+$. For a biset $\hat{X}$ and an edge-set/graph $J$ let $\delta_J(\hat{X})$ denote the set of edges in $J$ covering $\hat{X}$.

Given an instance of [SNA]{} and a biset $\hat{X}$ on $V$, let the requirement of $\hat{X}$ be $r(\hat{X})=\max\{r_{uv}: uv \in \delta_D(\hat{X})\}$ if $\delta_D(\hat{X}) \neq \emptyset$ and $r(\hat{X})=0$ otherwise. By the $q$-connectivity version of Menger’s Theorem (c.f. [@KN-sur]), $I \subseteq F$ is a feasible solution to an [SNA]{} instance if, and only if, $|\delta_I(\hat{X})| \geq h(\hat{X})$ for every bisets $\hat{X}$ on $V$, where $h$ is a biset-function defined by $$\label{e:p}
h(\hat{X})= \max\{r(\hat{X})-(q(\Gamma(\hat{X}))+|\delta_G(\hat{X})|),0\}$$ Let ${\cal P}_h$ denote the polytope of “fractional edge-covers” of $h$, namely, $${\cal P}_h=\left\{x \in \mathbb{R}^F:
x\left(\delta_F(\hat{Y})\right) \geq h(\hat{Y}) \ \forall \mbox{ biset } \hat{Y} \mbox{ on } V, \
0 \leq x_e \leq 1 \ \forall e \in F\right\} \ .$$ Let $\tau^*(h)$ denote the optimal value of a standard LP-relaxation for edge covering $h$ by a minimum cost edge set, namely, $\tau^*(h)=\min\left\{\sum_{e \in F} c_e x_e: x \in {\cal P}_h \right\}$. As an intermediate problem, we consider [SNA]{} instances when we seek to increase the connectivity by $1$ for every $uv \in D$, namely, when $r_{uv} = \lambda^q_G(u,v)+1$ for all $uv \in D$.

Given a [$D$-SNA]{} instance, we say that a biset $\hat{X}$ is [*tight*]{} if $h(\hat{X})=1$, where $h$ is defined by (\[e:p\]). [$D$-SNA]{} is equivalent to the problem of finding a minimum cost edge-cover of the biset family ${\cal F}=\{\hat{X}:h(\hat{X})=1\}$ of tight bisets. Thus the following generic problem includes the [$D$-SNA]{} problem.

For a biset-family ${\cal F}$ let $\tau^*({\cal F})$ denote the optimal value of a standard LP-relaxation for edge covering ${\cal F}$ by a minimum cost edge set, namely, $\tau^*({\cal F})=\tau^*(h)$ for $h(\hat{X})=1$ if $\hat{X} \in {\cal F}$ and $h(\hat{X})=0$ otherwise.

\[p:scale\] Suppose that [$a$-Based $D$-SNA]{} with edge-costs admits a polynomial time algorithm that computes a solution of cost at most $\rho(k) \tau^*({\cal F})$, where ${\cal F}$ is the family of tight bisets. Then [$a$-Based SNA]{} admits a polynomial time algorithm that computes a solution $I$ such that:

-   For edge-costs, $c(I) \leq \tau^*(h) \cdot \sum_{\ell=1}^k \frac{\rho(\ell)}{k-\ell+1}$, where $h$ is defined by (\[e:p\]).

-   For node-costs, $c(I) \leq {\sf opt} \cdot \sum_{\ell=1}^k \rho(\ell) \cdot \min\left\{\frac{p_{\max}}{k-\ell+1},1\right\}$.

We start with the edge-costs case. Consider the following sequential algorithm. Start with $I=\emptyset$. At iteration $\ell=1, \ldots,k$, add to $I$ and remove from $F$ an edge-set $I_\ell \subseteq F$ that increases by $1$ the $q$-connectivity of $G+I$ on the set of demand edges $D_\ell=\{sv:\lambda_{G+I}^q(s,v)=r(s,v)-k+\ell-1, sv \in D\}$, by covering the corresponding biset-family ${\cal F}_\ell$ using the $\rho$-approximation algorithm. After iteration $\ell$, we have $\lambda_{G+I}^q(s,v) \geq r(s,v)-k+\ell$ for all $sv \in D$. Consequently, after $k$ iterations $\lambda_{G+I}^q(s,v) \geq r(s,v)$ holds for all $sv \in D$, thus the computed solution is feasible. The approximation ratio follows from the following two observations.

-   $c(I_\ell) \leq \rho(\ell) \cdot \tau^*({\cal F}_\ell)$. This is so since $\lambda(s,v) \leq \ell-1$ for every $sv \in D_\ell$, hence the maximum requirement at iteration $\ell$ is at most $\ell$.

-   $\tau^*({\cal F}_\ell) \leq \frac{\tau^*(h)}{k-\ell+1}$. To see this, note that if $\hat{Y} \in {\cal F}_\ell$ and $x \in {\cal P}_h$ then $x(\delta(\hat{Y})) \geq k-\ell+1$, by Menger’s Theorem. Thus $x/(k-\ell+1)$ is a feasible solution for the LP-relaxation for edge-covering ${\cal F}_\ell$, of value $c \cdot x/(k-\ell+1)$.

Consequently, $c(I) = 
\sum_{\ell=1}^k c(I_\ell) \leq \sum_{\ell=1}^k \rho(\ell) \cdot \frac{\tau^*(h)}{k-\ell+1}=
\tau^*(h) \cdot \sum_{\ell=1}^k \frac{\rho(\ell)}{k-\ell+1}$.

Now let us consider the case of node-costs. Then we convert node-costs into edge-costs by assigning to every edge $e=av$ the cost $c'(e)=c(v)$. Let ${\sf opt}'$ denote the optimal solution value of the edge-costs instance obtained. Clearly, ${\sf opt} \leq {\sf opt}' \leq p_{\max} \cdot {\sf opt}$. Note that any inclusion minimal solution to an [$a$-Based $D$-SNA]{} instance has no parallel edges. This implies that $c(I_\ell) \leq \rho(\ell) \cdot {\sf opt}$ and that $c(I_\ell)=c'(I_\ell)$. The latter implies $c(I_\ell)=c'(I_\ell) \leq \rho(\ell) \cdot \frac {{\sf opt}'}{k-\ell+1} \leq 
\rho(\ell) \cdot {\sf opt} \cdot \frac {p_{\max}}{k-\ell+1}$, and the statement for the node-costs case follows.

In the next section we prove the following theorem, that together with Proposition \[p:scale\] finishes the proof of Theorem \[t:main’\].

\[t:D\] For edge-costs, undirected [$a$-Based $D$-SNA]{} admits a polynomial time algorithm that computes a feasible solution $I$ of cost $c(I) \leq H(\Delta_k) \cdot \tau^*({\cal F})$, and $c(I) \leq H(2k-1) \cdot \tau^*({\cal F})$ if $D$ is a star with center $s=a$, where ${\cal F}$ is the family of tight bisets.

Proof of Theorem \[t:D\]
========================

Recall that [$D$-SNA]{} reduces to [Biset-Family Edge-Cover]{} with ${\cal F}$ being the family of tight bisets; in the case of rooted requirements, it is sufficient to cover the biset-family ${\cal F}^s=\{\hat{X} \in {\cal F}: s \in V \setminus X^+\}$. Biset-families arising from [SNA]{} instances have some special properties, that are summarized in the following definitions.

The intersection and the union of two bisets $\hat{X},\hat{Y}$ is defined by $\hat{X} \cap \hat{Y} = (X \cap Y, X^+ \cap Y^+)$ and $\hat{X} \cup \hat{Y} = (X \cup Y,X^+ \cup Y^+)$. The biset $\hat{X} \setminus \hat{Y}$ is defined by $\hat{X} \setminus \hat{Y}=(X \setminus Y^+,X^+ \setminus Y)$. We write $\hat{X} \subseteq \hat{Y}$ and say that [*$\hat{Y}$ contains $\hat{X}$*]{} if $X \subseteq Y$ and $X^+ \subseteq Y^+$. Let ${\cal C}_{\cal F}$ denote the inclusion-minimal bisets in ${\cal F}$.

\[d:uncrossable\] Two bisets $\hat{X},\hat{Y}$ covered by an edge-set $D$ are [*$D$-independent*]{} if for any $xx',yy' \in D$ such that $xx'$ covers $\hat{X}$ and $yy'$ covers $\hat{Y}$, $\{x,x'\} \cap \Gamma(\hat{Y}) \neq \emptyset$ or $\{y,y'\} \cap \Gamma(\hat{X}) \neq \emptyset$; otherwise, $\hat{X},\hat{Y}$ are [*$D$-dependent*]{}. We say that a biset family ${\cal F}$ is [*$D$-uncrossable*]{} if $D$ covers ${\cal F}$ and if for any $D$-dependent $\hat{X},\hat{Y} \in {\cal F}$ the following holds: $$\label{e:uncross}
\hat{X} \cap \hat{Y},\hat{X} \cup \hat{Y} \in {\cal F} \mbox{ or }
\hat{X} \setminus \hat{Y},\hat{Y} \setminus \hat{X} \in {\cal F} \ .$$ Similarly, given a set $T \subseteq V$ of terminals, we say that $\hat{X}, \hat{Y}$ are [*$T$-independent*]{} if $X \cap T \subseteq \Gamma(\hat{Y})$ or if $Y \cap T \subseteq \Gamma(\hat{X})$, and $\hat{X},\hat{Y}$ are [*$T$-dependent*]{} otherwise. We say that ${\cal F}$ is $T$-uncrossable if $T$ covers the set-family of the inner parts of ${\cal F}$, and if (\[e:uncross\]) holds for any $T$-dependent $\hat{X},\hat{Y} \in {\cal F}$.

A biset-family ${\cal F}$ is symmetric if $\hat{X} \in {\cal F}$ implies $(V \setminus X^+,V \setminus X) \in {\cal F}$. Clearly, the family of tight bisets is symmetric. We will use the the following fundamental statement, that was implicitly proved in [@N-aug].

\[[@N-aug]\] The family ${\cal F}$ of tight bisets is $D$-uncrossable, and if $D$ is a star with center $s$ and leaf-set $T$ then $\{\hat{X} \in {\cal F}: s \notin X^+\}$ is $T$-uncrossable.

For a biset-family ${\cal C}$ let $\gamma_{\cal C}=\max\{|\Gamma(\hat{C})|: \hat{C} \in {\cal C}\}$. Note that if ${\cal F}$ is the family of tight bisets then $\gamma_{\cal F} \leq k-1$. Given an instance of [Biset-Family Edge-Cover]{}, we will assume that the family ${\cal C}$ of the inclusion members of ${\cal F}$ can be computed in polynomial time. We note that for ${\cal F}$ being the family of tight sets, this step can be implemented in polynomial time, c.f. [@N-aug]. Under this assumption, we prove the following generalization of Theorem \[t:D\].

\[t:main\] For edge/node-costs, [$a$-Based Biset-Family Edge-Cover]{} admits a polynomial time algorithm that computes a cover $I$ of ${\cal F}$ such that:

-   $c(I) \leq H\left({(4\gamma_{\cal C}+1)}^2\right) \cdot \tau^*({\cal F})$ if ${\cal F}$ is symmetric and $D$-uncrossable.

-   $c(I) \leq H(2\gamma_{\cal C}+1) \cdot \tau^*({\cal F})$ if ${\cal F}$ is $T$-uncrossable and $a \in V \setminus X^+$ for all $\hat{X} \in {\cal F}$.

In the rest of this section we prove Theorem \[t:main\].

A node set $U \subseteq V$ is a [${\cal C}$-transversal]{} of a hypergraph (set-family) ${\cal C}$ on $V$ if $U$ intersects every set in ${\cal C}$; if ${\cal C}$ is a biset-family then $U$ should intersect the inner part of every member of ${\cal C}$. Given costs $\{c_v:v \in V\}$, let $t^*({\cal C})$ denote the minimum value of a fractional ${\cal C}$-transversal, namely: $$t^*({\cal C})=\min\{\sum_{v \in V} c_v x_v: 
x(C) \geq 1 \ \ \forall \hat{C} \in {\cal C}, \ x(v) \geq 0 \ \forall v \in V\} \ .$$

In [@N-aug], the following is proved.

\[[@N-aug]\] \[t:2\] Let ${\cal F}$ be a biset-family and let ${\cal C}$ be the family of the inclusion members of ${\cal F}$. Then the maximum degree in the hypergraph $\{C:\hat{C} \in {\cal C}\}$ is at most:

-   ${(4\gamma_{\cal C}+1)}^2$ if ${\cal F}$ is $D$-uncrossable.

-   $2\gamma_{\cal C}+1$ if ${\cal F}$ is $T$-uncrossable.

Given a hypergraph $(V,{\cal C})$ with node-costs, the greedy algorithm computes in polynomial time a ${\cal C}$-transversal $U \subseteq V$ of cost $c(U) \leq H(\Delta({\cal C})) t^*({\cal C})$, where $\Delta({\cal C})$ is the maximum degree of the hypergraph (c.f. [@Lov]).

\[l:ratio\] If an edge-set $I$ covers a biset-family ${\cal F}$ then the set of endnodes of $I$ is a transversal of ${\cal F}$.

\[l:feasible\] Let ${\cal F}$ be a biset family on $V$ and $I$ a star with center $a$ on a transversal $U \subseteq V$ of ${\cal F}$. Then $I$ covers ${\cal F}$ in each one of the following cases.

-   ${\cal F}$ is symmetric and $a \notin \Gamma(\hat{X})$ for all $\hat{X} \in {\cal F}$.

-   $a \in V \setminus X^+$ for all $\hat{X} \in {\cal F}$.

Let $\hat{X} \in {\cal F}$. Then $a \in X$ or $a \in V \setminus X^+$. If $a \in V \setminus X^+$, then since $U$ is a transversal of ${\cal C}$, there is $u \in U \cap X$. If $a \in X$, then if ${\cal F}$ is symmetric, then there $u \in U \cap (V \setminus X^+)$. In both cases, there is an edge $au \in I$, and this edge covers $\hat{X}$.

The algorithm as in Theorem \[t:main\], for both edge-costs and node-costs is as follows, where in the case of node-costs we may assume that the cost of $a$ is zero.

The solution computed is feasible by Lemma \[l:feasible\]. The approximation ratio follows from Theorem \[t:2\] and Lemma \[l:ratio\].\

Proof of Theorem \[t:fc-bounds\] {#s:fc-bounds}
================================

[SSL with Flow-Cost Bounds]{} is a special case of the following generalization of [Submodular Cover]{}, where we have two progress functions: $$f(S)= \sum_{v \in V}\min\{\lambda^{p,q}_G(S,v),d_v\}  \ \mbox{ and} \ 
  g(S)= \sum_{v \in V}\min\{-\mu^{p,q}_G(S,v),-b_v\} .$$ It is easy to see that $S$ is a feasible solution to [SSL with Flow-Cost Bounds]{} if and only if both $f(S)=f(V)=\sum_{v \in V} d_v$ and $g(S)=g(V)=-\sum_{v \in V} b_v$. Note that $\max_{u \in U} f(\{u\})-f(\emptyset) \leq d(V)$, and that $\max_{u \in U} g(\{u\})-g(\emptyset) \leq c(E)$ if $g(\emptyset) \neq -\infty$. The function $f$ is submodular since for any $v \in V$ the function $f_v(S)=\lambda^{p,q}_G(S,v)$ is submodular, as can be deduced from Lemmas \[l:star\] and \[l:max\]. The function $g$ is submodular since for any $v \in V$ the function $g_v(S)=\lambda^{p,q}_G(S,v)$ is submodular; this is proved in [@BKP] for the case of edge-connectivity, and the proof for $(p,q)$-connectivity is similar. Also, both functions are non-decreasing and admit a polynomial time evaluation oracle.

There are several natural approaches to solve the [Double Submodular Cover]{} problem using the greedy algorithm of Wolsey [@W]. One is to apply the greedy algorithm with the function $f+g$. Another possibility is to solve two instances of [Submodular Cover]{}, one with function $f$ and the other with function $g$, returning the union of the solutions $S_f$ and $S_g$ computed. However, in both case the ratio guarantee may be unbounded if $g(\emptyset)=-\infty$, which happens in the case of [SSL with Flow-Cost Bounds]{}.

Note that in [Double Submodular Cover]{} instances that arise from [SSL with Flow-Cost Bounds]{} have the following property: if $f(S_f)=f(U)$ then $g(S_f) \neq -\infty$ for any $S \supseteq S_f$. Therefore, the following approach works. We take the set $S_f$ into our solution, and consider the residual [Submodular Cover]{} problem with groundset $V \setminus S_f$ and set function $h(S)=g(S_f \cup S)$, $S \subseteq V \setminus S_f$. The function $h$ is submodular if $g$ is, and we get approximation ratio $$H\left(\max_{v \in V} f(\{v\})-f(\emptyset)\right)+H\left(\max_{v \in V} h(\{v\})-h(\emptyset)\right)
\leq H(d(V))+H(c(E)) \ .$$

Clearly, the approach described can be generalized to the case when we have many non-decreasing submodular functions, under the assumption that there exists an ordering $f_1,f_2, \ldots$ of the functions such that for any $i$, if $f_j(S)=f(U)$ for every $j \leq i$, then $f_{j+1}(S') \neq -\infty$ for any $S' \supseteq S$.

[**Acknowledgment**]{} The second author thank Takuro Fukunaga and an anonymous referee for many useful comments.

[10]{}

K. Arata, S. Iwata, K. Makino, and S. Fujishige. Locating sources to meet flow demands in undirected networks. , 42:54––68, 2002.

J. Bar-Ilan, G. Kortsarz, and D. Peleg. Generalized submodular cover problems and applications. , 250(1-2):179–200, 2001.

M. Barasz, J. Becker, and A. Frank. An algorithm for source location in directed graphs. , 33:221––230, 2005.

A. Frank. Augmenting graphs to meet edge-connectivity requirements. , 5(1):25–53, 1992.

A. Frank and E. Tardos. An application of submodular flows. , 114/115:329–348, 1989.

T. Fukunaga. Approximating minimum cost source location problems with local vertex-connectivity demands. In [*TAMC*]{}, pages 428–439, 2011.

T. Ishii. Greedy approximation for source location problem with vertex-connectivity requirements in undirected graphs. , 7:570–578, 2009.

T. Ishii, H. Fujita, and H. Nagamochi. Source location problem with local [$3$]{}-vertex-connectivity requirements. In [*Proc. 3rd Hungarian–Japanese Symposium on Discrete Mathematics and Its Applications*]{}, pages 368––377, 2003.

T. Ishii, H. Fujita, and H. Nagamochi. Minimum cost source location problem with local [$3$]{}-vertex-connectivity requirements. , 372:81––93, 2007.

T. Ishii and K. Makino. Posi-modular systems with modulotone requirements under permutation constraints. , 2(1):61–76, 2010.

H. Ito, M. Ito, Y. Itatsu, H. Uehara, and M. Yokoyama. Source location problems considering vertex-connectivity and edge-connectivity simultaneously. , 40:63––70, 2002.

H. Ito, K. Makino, K. Arata, S. Honami, Y. Itatsu, and S. Fujishige. Source location problem with flow requirements in directed networks. , 18(4):427––435, 2003.

G. Kortsarz and Z. Nutov. PWS, 2007.

G. Kortsarz and Z. Nutov. Tight approximation algorithm for connectivity augmentation problems. , 74(5):662–670, 2008.

L. Lovász. On the ratio of optimal integral and fractional covers. , 13:383–390, 1975.

S. Mamada, T. Uno, K. Makino, and S. Fujishige. An [$O(n\log^2 n)$]{} algorithm for the optimal sink location problem in dynamic tree networks. , 154(16):2387–2401, 2006.

H. Nagamochi and T. Ibaraki. . Cambridge University Press, 2008.

H. Nagamochi, T. Ishii, and H. Ito. Minimum cost source location problem with vertex-connectivity requirements in digraphs. , 80:287––294, 2001.

Z. Nutov. Approximating minimum cost connectivity problems via uncrossable bifamilies. To appear in [*Transactions on Algorithms*]{}. Preliminary version in [*FOCS*]{} 2009, 417–426.

Z. Nutov. Approximating node-connectivity augmentation problems. , 63(1-2):398–410, 2012.

M. Sakashita, K. Makino, and S. Fujishige. Minimum cost source location problems with flow requirements. , 50:555–583, 2008.

M. Sakashita, K. Makino, H. Nagamochi, and S. Fujishige. Minimum transversals in posi-modular systems. , 23:858–871, 2009.

A. Schrijver. . Springer, 2004.

H. Tamura, M. Sengoku, S. Shinoda, and T. Abe. Location problems on undirected flow networks. , E73:1989––1993, 1990.

L. A. Wolsey. An analysis of the greedy algorithm for the submodular set covering problem. , 2:385––393, 1982.
