claim that each iteration step runs in $O(c)$ time. Computing the SCCs of $H^{\mathrm{aux}}$ takes $O(c)$ time because $H^{\mathrm{aux}}$ contains $c$ vertices and at most $2c - 2$ arcs and the algorithm spends $O(c)$ time to compute the cost of $H$ and update $OptCost$ and connection $\mathcal{C}$. Constructing the output graph takes $O(n + m)$ time. Thus, the overall running time is $O(n + m + 4^c \cdot c^{2c - 3/2})$.

Combining we arrive at our main theorem of this section.

\[thm:SCC-Algo\] <span style="font-variant:small-caps;">MinPAC</span> can be solved in $O(c^2 \cdot 2^c \cdot n + m + 4^c \cdot c^{2c - 3 / 2})$ time.

Let $(G, w)$ be an instance of <span style="font-variant:small-caps;">MinPAC</span>. We run sequentially to obtain an optimal solution $H$ of $({G_\ell^{\operatorname{rel}}}, {w_\ell^{\operatorname{rel}}})$. Since ${G_\ell^{\operatorname{rel}}}$ is a relevant subgraph of $G$ it follows from that the graph $H$ is also an optimal solution of $(G, w)$.

The overall running time is then $$\begin{aligned}
    O(cn + m) + O(2^c \cdot c^2 \cdot n) + O(n + m + 4^c \cdot c^{2c - 3/2}) \\
    = O(c^2 \cdot 2^c \cdot n + m + 4^c \cdot c^{2c - 3 / 2}).
  \end{aligned}$$ This concludes the proof of the theorem.

Parameterization 