2026-08-02T16:48:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20578 2024-08-23T05:50:28Z ddc:004 open_access

Graph Search Trees and the Intermezzo Problem Beisegel, Jesse Köhler, Ekkehard Ratajczak, Fabienne Scheffler, Robert Strehler, Martin graph search trees intermezzo problem algorithm parameterized complexity 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 NP-complete. We utilize this finding to strengthen a complexity result from order theory. Given a partial order π and a set of triples, the 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 NP-complete even when the Hasse diagram of the partial order forms a tree of bounded height. In contrast, we give an XP-algorithm for the problem when parameterized by the width of the partial order. Furthermore, we show that - under the assumption of the Exponential Time Hypothesis - the running time of this algorithm is asymptotically optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jesse Beisegel and Ekkehard Köhler and Fabienne Ratajczak and Robert Scheffler and Martin Strehler 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.22 urn:nbn:de:0030-drops-205781 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.22 eng https://creativecommons.org/licenses/by/4.0/legalcode