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 