Graph Search Trees and the Intermezzo Problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911999832621056 |
|---|---|
| author | Beisegel, Jesse Köhler, Ekkehard Ratajczak, Fabienne Scheffler, Robert Strehler, Martin |
| author_facet | Beisegel, Jesse Köhler, Ekkehard Ratajczak, Fabienne Scheffler, Robert Strehler, Martin |
| contents | 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 $π$ and a set of triples, the $\mathsf{NP}$-complete intermezzo problem asks for a linear extension of $π$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_18645 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph Search Trees and the Intermezzo Problem Beisegel, Jesse Köhler, Ekkehard Ratajczak, Fabienne Scheffler, Robert Strehler, Martin Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics 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 $π$ and a set of triples, the $\mathsf{NP}$-complete intermezzo problem asks for a linear extension of $π$ 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. |
| title | Graph Search Trees and the Intermezzo Problem |
| topic | Discrete Mathematics Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2404.18645 |