Search Results

Documents authored by Bourotte, Codaline

Document
DOI: 10.4230/LIPIcs.MFCS.2026.7
A Congestion Parameter for Depth-First Graph Traversals

Authors: Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, and Shinnosuke Seki

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract
We explore a new graph parameter, KLX number, which quantifies the minimum edge congestion of depth-first search (DFS) traversals of a given graph. Originally motivated by a problem in RNA nanostructure design, this parameter is also of independent theoretical interest. Informally, the KLX number of a graph is defined as the minimum, over all its DFS traversals, of the maximum number of back edges that are simultaneously open during the traversal. We provide full characterisations and linear-time recognition algorithms for graphs with KLX numbers 0, 1 and 2. We also relate KLX to tree-width, proving that any graph satisfies TW ≤ KLX+1. Furthermore, we show that the property KLX ≤ k is MSO₂-expressible for every fixed k. Combined with the tree-width bound, this result implies that determining whether a graph has KLX number at most k can be achieved in linear time for any constant k.
Cite as

Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, and Shinnosuke Seki. A Congestion Parameter for Depth-First Graph Traversals. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 7:1-7:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bourotte_et_al:LIPIcs.MFCS.2026.7,
  author =	{Bourotte, Codaline and Ducloz, Gwendal and Orponen, Pekka and Seki, Shinnosuke},
  title =	{{A Congestion Parameter for Depth-First Graph Traversals}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{7:1--7:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.7},
  URN =		{urn:nbn:de:0030-drops-273889},
  doi =		{10.4230/LIPIcs.MFCS.2026.7},
  annote =	{Keywords: KLX, depth-first search, DFS trees, k-connectedness, tree-width, parameterised complexity, monadic second-order logic, Courcelle’s theorem, RNA nanotechnology}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact