\[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 