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 