and the statement for the node-costs case follows.

In the next section we prove the following theorem, that together with Proposition \[p:scale\] finishes the proof of Theorem \[t:main’\].

\[t:D\] For edge-costs, undirected [$a$-Based $D$-SNA]{} admits a polynomial time algorithm that computes a feasible solution $I$ of cost $c(I) \leq H(\Delta_k) \cdot \tau^*({\cal F})$, and $c(I) \leq H(2k-1) \cdot \tau^*({\cal F})$ if $D$ is a star with center $s=a$, where ${\cal F}$ is the family of tight bisets.

Proof of Theorem \[t:D\]
========================

Recall that [$D$-SNA]{} reduces to [Biset-Family Edge-Cover]{} with ${\cal F}$ being the family of tight bisets; in the case of rooted requirements, it is sufficient to cover the biset-family ${\cal F}^s=\{\hat{X} \in {\cal F}: s \in V \setminus X^+\}$. Biset-families arising from [SNA]{} instances have some special properties, that are summarized in the following definitions.

The intersection and the union of two bisets $\hat{X},\hat{Y}$ is defined by $\hat{X} \cap \hat{Y} = (X \cap Y, X^+ \cap Y^+)$ and $\hat{X} \cup \hat{Y} = (X \cup Y,X^+ \cup Y^+)$. The biset $\hat{X} \setminus \hat{Y}$ is defined by $\hat{X} \setminus \hat{Y}=(X \setminus Y^+,X^+ \setminus Y)$. We write $\hat{X} \subseteq \hat{Y}$ and say that [*$\hat{Y}$ contains $\hat{X}$*]{} if $X \subseteq Y$ and 