Graph Search Trees and the Intermezzo Problem
<|reference_start|>Graph Search Trees and the Intermezzo Problem: 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 a 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.<|reference_end|>
@article{beisegel2024graph,
    title={Graph Search Trees and the Intermezzo Problem},
    author={Jesse Beisegel, Ekkehard K"ohler, Fabienne Ratajczak, Robert
  Scheffler, and Martin Strehler},
    journal={arXiv preprint arXiv:2404.18645},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.18645},
    primaryClass={cs.DM cs.CC cs.DS math.CO}
}