DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2024.22

Graph Search Trees and the Intermezzo Problem

Authors: Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler, and Martin Strehler

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

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 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.

Cite as

Jesse Beisegel, Ekkehard Köhler, Fabienne Ratajczak, Robert Scheffler, and Martin Strehler. Graph Search Trees and the Intermezzo Problem. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{beisegel_et_al:LIPIcs.MFCS.2024.22,
  author =	{Beisegel, Jesse and K\"{o}hler, Ekkehard and Ratajczak, Fabienne and Scheffler, Robert and Strehler, Martin},
  title =	{{Graph Search Trees and the Intermezzo Problem}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.22},
  URN =		{urn:nbn:de:0030-drops-205781},
  doi =		{10.4230/LIPIcs.MFCS.2024.22},
  annote =	{Keywords: graph search trees, intermezzo problem, algorithm, parameterized complexity}
}

Search Results

Documents authored by Ratajczak, Fabienne

Graph Search Trees and the Intermezzo Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message