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}$, 