a connector of minimum cost for each $S \in \mathcal{S}_{G_\ell}$ and each subset $\mathcal{T} \subseteq {\mathcal{S}_{G,\ell}^{\operatorname{reach}}}(S)$. This allows us to compute an optimal solution with exhaustive search on connections between SCCs in the last phase.

\[def:mcc\] Let $(G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span> and let $\ell$ be a vertex lower bound. A minimum-cost connector is a function $\operatorname{MCC}\colon \mathcal{S}_{G_\ell} \times 2^{\mathcal{S}_{G_\ell}} \to 2^{A({G_\ell^{\operatorname{rel}}})}$ such that for any $S \in \mathcal{S}_{G_\ell}$ and any $\mathcal{T} \subseteq {\mathcal{S}_{G,\ell}^{\operatorname{reach}}}(S)$ the following properties are satisfied:

1.  For any $S' \in \mathcal{T}$, there exist vertices $v \in S$ and $u \in S'$ with $vu \in \operatorname{MCC}(S, \mathcal{T})$.\[def:mcc1\]

2.  There is no subset $B \subseteq A({G_\ell^{\operatorname{rel}}})$ that satisfies the above property and that satisfies $\operatorname{Cost}(S, B, {w_\ell^{\operatorname{rel}}}) < \operatorname{Cost}(S, \operatorname{MCC}(S, \mathcal{T}), {w_\ell^{\operatorname{rel}}})$.

computes a minimum-cost connector. For each SCC $S \in \mathcal{S}_{G_\ell}$, we employ dynamic programming over vertices in $S$ and subsets of $\mathcal{S}_{G_\ell}$. This gives us a significant speed-up compared to the naïve approach of branching into at worst $c$ different neighbors on each vertex: from $n^{\theta(c)}$ time to $O(2^c \cdot c^2 \cdot n)$ time.

\[lemma:dp\] Given a relevant subgraph ${G_\ell^{\operatorname{rel}}}$ and a relevant weight function ${w_\ell^{\operatorname{rel}}}$, computes a minimum-cost connector $\operatorname{MCC}$ in $O(2^c 