The algorithm for finding a smallest pre-feasible function \(\bar{f}\)  described in [1]} consists of several iterations.
In each iteration, we find a violating path \(\pi \)  and reset the string \(f(F^{\prime })\)  as the shortest string \(x\)  which makes \(x^{-1}\cdot \phi (\pi ) \cdot f(F) \in \Gamma (\pi )\)  if \(\pi \)  belongs to the first case of Lemma REF .
Otherwise, we reset \(f(F)\)  as the as the shortest string \(x\)  which makes \(x^{-1}\cdot \phi (\pi ^{-1}) \cdot f(F^{\prime }) \in \Gamma (\pi )\) .
We repeat this procedure until \(f(\cdot )\)  becomes pre-feasible.
The analysis of [1]} shows that
one can find a smallest pre-feasible function \(\bar{f}\)  of \(f\) 
in \(O(n^4)\)  time (assuming \(\mathcal {A}\)  has size \(O(n^2)\) , the size of \(|\Gamma (\cdot )|\)  is constant.)
However, in Section REF , we show that
this procedure takes \(2^{O(k)}n\)  time in our case
due to the properties of \(\mathcal {W}\) .
