We first construct a backbone structure (a subgraph of \(G^\textsf {rad}\) ) of complexity of \(2^{O(k)}\)  in \(2^{O(k)}n\)  time, and then show that all paths of \(\mathcal {P}\)  can be pushed onto the backbone structure (and several precomputed paths) for a \(T\) -linkage \(\mathcal {P}\) . In this paper, we call this backbone structure the frames and skeleton forests, which will be defined later.
In this way, each edge on the backbone structure is traversed by the resulting walks \(2^{O(k)}\)  times in total.
Also, each edge on the precomputed paths is traversed by the resulting walks at most once in total.
This allows us to only consider the weak \(T\) -linkages using each edge of the backbone structure \(2^{O(k)}\)  times and each edge of the precomputed paths exactly once.
There are \(2^{O(k^2)}\)  such weak \(T\) -linkages \(\mathcal {W}\) , and we can enumerate each of them in \(2^{O(k)}n\)  time.
By slightly modifying \(G\)  with respect to a given weak \(T\) -linkage, we can make each vertex of the backbone structure
have degree \(2^{O(k)}\)  (without changing the answer of the instance).
Then the number \(\chi \)  of face-edge paths \(\pi \)  of \(\Pi \)  with \(\phi (\pi )\notin \Gamma (\pi )\)  decreases to \(2^{O(k)}\) .
In this way, we can overcome the second obstacle: we can construct the backbone structure in \(2^{O(k)}n\)  time (although we define the backbone structure in a different way.)
Also, we can partially overcome the third obstacle: now the algorithm of [1]} takes \(O(n^5)\)  time in our case.
