removes all but one minimum-weight arc that share the initial vertex and the SCC the terminal vertex belongs to.

We show subsequently that the resulting instance of <span style="font-variant:small-caps;">MinPAC</span> satisfies the properties listed in the next definition.

\[def:rel\] Let $(G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span> and let $\ell$ be a lower bound. We say that a graph ${G_\ell^{\operatorname{rel}}}$ and a weight function ${w_\ell^{\operatorname{rel}}}$ with $V(G) = V({G_\ell^{\operatorname{rel}}})$, $A({G_\ell^{\operatorname{rel}}}) \subseteq A(G)$, and ${w_\ell^{\operatorname{rel}}}\colon A({G_\ell^{\operatorname{rel}}}) \to {\mathds{N}}$ are *a relevant subgraph* and *relevant weight function* induced by $\ell$, respectively, if they satisfy the following properties:

1.  $\operatorname{OPT}((G, w)) = \operatorname{OPT}(({G_\ell^{\operatorname{rel}}}, {w_\ell^{\operatorname{rel}}}))$.

2.  For any SCC $S \in \mathcal{S}_{G_\ell}$, it holds that $G[S] = {G_\ell^{\operatorname{rel}}}[S]$.\[def:rel2\]

3.  For any SCC $S \in \mathcal{S}_{G_\ell}$ and any vertex $v \notin S$, it holds that $|\{ vu \in A({G_\ell^{\operatorname{rel}}}) \mid u \in S \}| \le 1$.

Since it follows from property \[def:rel2\] that $\mathcal{S}_{G_\ell} = \mathcal{S}_{{G_\ell^{\operatorname{rel}}}}$, we will use them interchangeably.

\[scc:ared\] Let $(G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span> and let $\ell$ be a vertex lower bound. computes in $O(m)$ time a relevant subgraph ${G_\ell^{\operatorname{rel}}}$ and a relevant weight function ${w_\ell^{\operatorname{rel}}}$ induced by $\ell$.

For any $v \in V(G)$ and any $S \in 