\mathcal{S}_{G_\ell}$, sets $M(v, S)$ to a minimum-weight arc from $v$ to a vertex in $S$ in the first iteration. In the second iteration, every arc $vu$ is removed unless $v$ and $u$ belong to the same SCC or $M(v, S_u)$ is set to $vu$. Recall that the optimal cost remains the same after arc removals as shown in . Thus, returns an instance of <span style="font-variant:small-caps;">MinPAC</span> $({G_\ell^{\operatorname{rel}}}, {w_\ell^{\operatorname{rel}}})$ that satisfies the aforementioned properties. The algorithm spends $O(m)$ time on initializing $M$ () and $O(m)$ time on the iteration over the arcs ().

#### Phase 2.

In this phase, we aim to compute an optimal set of arcs to connect each SCC to all other SCCs. We start with some notation.

Let ${G_\ell^{\operatorname{rel}}}$ be a relevant subgraph. For any $S \in \mathcal{S}_{G_\ell}$, we define the set of SCCs reachable from $S$ via an arc as $${\mathcal{S}_{G,\ell}^{\operatorname{reach}}}(S) = \{ S' \in \mathcal{S}_{G_\ell} \setminus \{ S \} \mid \exists vu \in A({G_\ell^{\operatorname{rel}}}).\; v  \in S \wedge u \in S' \}.$$

We say that an arc set $B$ is a *connector* if $B$ connects some SCC $S$ to some set $\mathcal{T} \subseteq {\mathcal{S}_{G,\ell}^{\operatorname{reach}}}(S)$ of SCCs reachable from $S$. Then, our goal is to find 