1. Graph Search Trees and the Intermezzo Problem
- Author
-
Beisegel, Jesse, Köhler, Ekkehard, Ratajczak, Fabienne, Scheffler, Robert, and Strehler, Martin
- Subjects
Computer Science - Discrete Mathematics ,Computer Science - Computational Complexity ,Computer Science - Data Structures and Algorithms ,Mathematics - Combinatorics - Abstract
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., Comment: full version of an extended abstract published in the Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) in Bratislava
- Published
- 2024