have $v_i$ as their initial vertex. We distinguish two cases depending on whether $B_{i}'$ is empty.

Case 1. If $B_{i}' = \emptyset$, then $B'$ consists of arcs whose initial vertices are in $\{ v_1 \dots, v_{i - 1} \}$. Then, we have $$\operatorname{Cost}(S, B', {w_\ell^{\operatorname{rel}}}) \ge \operatorname{Cost}(S, D_{i - 1}(\mathcal{T}_{B'}), {w_\ell^{\operatorname{rel}}}) \ge \operatorname{Cost}(S, D_i(\mathcal{T}_{B'}), {w_\ell^{\operatorname{rel}}}).$$ Here the first inequality follows from the induction hypothesis, and the second inequality follows from the assignment on because $\mathcal{T}_{B'} \subseteq \mathcal{T}_{B_{i-1}}$.

Case 2. If $B_{i}' \ne \emptyset$, then the cost of $S$ associated with $B'$ is $$\begin{aligned}
    \operatorname{Cost}(S, B', {w_\ell^{\operatorname{rel}}})
    &\ge \operatorname{Cost}(S, \mathcal{D}_{i - 1}(\mathcal{T}_{B'} \setminus \mathcal{T}_{B_i'}), {w_\ell^{\operatorname{rel}}}) + \max_{v_i u \in B_{i}'} {w_\ell^{\operatorname{rel}}}(v_i u) \\ 
    &\ge \operatorname{Cost}(S, D_i(\mathcal{T}_{B'}), {w_\ell^{\operatorname{rel}}}).
  \end{aligned}$$ Here the first inequality follows from the induction hypothesis, and the second inequality follows from the assignment on . In both cases, we have $\operatorname{Cost}(S, B', {w_\ell^{\operatorname{rel}}}) \ge \operatorname{Cost}(S, D_i(\mathcal{T}_{B'}), {w_\ell^{\operatorname{rel}}})$, and thus a contradiction is reached.

It remains to analyze the running time. In the initialization phase, we iterate over all vertices () and all subsets of $\mathcal{T}_{B_i}$ (). Note that $|\mathcal{T}_{B_i}| \le |\mathcal{S}_{G_\ell}| = c$ as shown in the above claim and hence there are at most $2^c$ subsets. Each iteration 