  The last in-tree recognition problem asks whether a given spanning tree can
be derived by connecting each vertex with its rightmost left neighbor of some
search ordering. In this study, we demonstrate that the last-in-tree
recognition problem for Generic Search is $\mathsf{NP}$-complete. We utilize
this finding to strengthen a complexity result from order theory. Given partial
order $\pi$ and a set of triples, the $\mathsf{NP}$-complete intermezzo problem
asks for a linear extension of $\pi$ where each first element of a triple is
not between the other two. We show that this problem remains
$\mathsf{NP}$-complete even when the Hasse diagram of the partial order forms a
tree of bounded height. In contrast, we give an $\mathsf{XP}$ algorithm for the
problem when parameterized by the width of the partial order. Furthermore, we
show that $\unicode{x2013}$ under the assumption of the Exponential Time
Hypothesis $\unicode{x2013}$ the running time of this algorithm is
asymptotically optimal.
