[step:Construct the split residual digraph for a fixed linkage of $I$]
Let $I,J \in \mathcal I$ satisfy $|I| < |J|$. Fix a linkage
\begin{align*}
\mathcal P = (P_i)_{i \in I}
\end{align*}
from $I$ to $T$. For each $i \in I$, write $t_i \in T$ for the terminal vertex of $P_i$, and define
\begin{align*}
T_{\mathcal P} = \{t_i : i \in I\}.
\end{align*}
We form a split directed graph $N_{\mathcal P}$. For each vertex $v \in V$, introduce two vertices $v^-$ and $v^+$ and a capacity arc
\begin{align*}
c_v := (v^-,v^+).
\end{align*}
For each directed arc $(u,v) \in A$, introduce the transit arc
\begin{align*}
a_{uv} := (u^+,v^-).
\end{align*}
Finally, introduce a new sink vertex $\omega$ and, for each terminal $t \in T$, a terminal arc
\begin{align*}
q_t := (t^+,\omega).
\end{align*}
The linkage $\mathcal P$ determines a family of arc-disjoint directed paths in $N_{\mathcal P}$ from the vertices $i^-$, with $i \in I$, to $\omega$: along a directed path
\begin{align*}
P_i = (v_0,v_1,\dots,v_m)
\end{align*}
with $v_0=i$ and $v_m=t_i$, the corresponding split path uses the arcs
\begin{align*}
c_{v_0}, a_{v_0v_1}, c_{v_1}, a_{v_1v_2}, \dots, a_{v_{m-1}v_m}, c_{v_m}, q_{v_m}.
\end{align*}
For a length-zero path at a terminal $i \in T$, the split path uses $c_i$ and $q_i$. Let $F_{\mathcal P}$ denote the set of all split arcs used by these paths.
Define the residual digraph $R_{\mathcal P}$ on the same vertex set as $N_{\mathcal P}$ as follows: every arc of $N_{\mathcal P} \setminus F_{\mathcal P}$ is kept with its original orientation, while every arc of $F_{\mathcal P}$ is replaced by the reverse arc. Thus unused capacity, transit, and terminal arcs may be used forward, and used arcs may be cancelled by traversing them backward.
Define the residual starting map
\begin{align*}
s_{\mathcal P}: V \to \{v^- : v \in V\}
\end{align*}
by $s_{\mathcal P}(x)=x^-$ for every $x \in V$. We always start at the incoming split vertex $x^-$; if $c_x$ is already used by the present linkage, the residual digraph records this by making the reverse arc $(x^+,x^-)$ available, so any rerouting through $x$ is handled by the ordinary residual-network operation rather than by changing the source vertex.
[/step]