$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 