$S$.

\[scc:arcred\] Let $(G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span> and let $\ell$ be a vertex lower bound. Let $S_v, S_u \in \mathcal{S}_{G_\ell}$ be two distinct SCCs and let $v \in S_v$ and $u, u' \in S_u$ be vertices of $G$ with $w(vu) \le w(vu')$. Then, it holds that $\operatorname{OPT}((G, w)) = \operatorname{OPT}((G - vu', w))$.

Observe that the removal of an arc does not decrease the cost of an optimal solution. Thus, $\operatorname{OPT}((G, w)) \le \operatorname{OPT}((G - vu', w))$. Let $H$ be an optimal solution of $(G, w)$. Suppose that $H$ contained $vu'$. The cost paid by $v$ in $H$ is then at least $w(vu')$. Since $u$ and $u'$ both belong to $S_u$, the subgraph $H' = H + vu - vu'$ is a strongly connected spanning subgraph. Since $w(vu) \le w(vu')$, it follows that $H'$ is optimal. Moreover, $H'$ is also a solution of $(G - vu', w)$, and thus $\operatorname{OPT}((G, w)) \ge \operatorname{OPT}((G - vu', w))$.

exhaustively removes all arcs $vu'$ which satisfy the preconditions of : The algorithm iterates over each arc in $G$ twice. It finds a minimum-weight arc from each vertex to each SCC in the first iteration. In the second iteration, it 