obtained from $(V(G), \bigcup^c_{i=1} \operatorname{MCC}(S_i, \mathcal{T}_{S_i}))$ by contracting each SCC of $G_\ell$ into a single vertex. Since our algorithm performs an exhaustive search, it finds a graph of cost $\operatorname{OPT}(({G_\ell^{\operatorname{rel}}}, {w_\ell^{\operatorname{rel}}}))$.

We now analyze the running time of the algorithm. For each $c \le k \le 2c - 2$, the number of sets of integers $\{ k_1, \dots, k_c \}$ that satisfy $k_i \ge 1$ for all $i \in [c]$ and $\sum^c_{i=1} k_i = k$ is $$\begin{aligned}
    \binom{k - 1}{c - 1} & \le \binom{2c - 3}{c - 1}
    = \frac{(2c - 3)!}{(c - 1)! \, (c - 2)!} \\
    &\in O\left( \frac{\sqrt{2c - 3}}{\sqrt{c - 1}\sqrt{c - 2}} \cdot \frac{(2c - 3)^{2c - 3}}{(c - 1)^{c - 1} (c - 2)^{c - 2}} \right)
    = O \left(\frac{4^c}{\sqrt{c}} \right),
  \end{aligned}$$ where the membership is due to Stirling’s approximation. For each fixed set of integers $\{k_1, \dots, k_c\}$, the number of sets $\{ \mathcal{T}_{S_1}, \dots, \mathcal{T}_{S_c} \}$ the algorithm generates is $$\begin{aligned}
    \prod^c_{i = 1} \binom{c}{k_i} \le \prod^c_{i =1} c^{k_i} = c^{\sum^c_{i=1} k_i} = c^k.
  \end{aligned}$$ So the total number of iterations () is $$\begin{aligned}
    O\left(\frac{4^c}{\sqrt{c}} \cdot \sum^{2c - 2}_{k = c} c^k\right)
    = O(4^c \cdot c^{2c - 5/2}).
  \end{aligned}$$ We 