2026-08-21T18:02:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27388 2026-08-21T14:42:37Z ddc:004 open_access

A Congestion Parameter for Depth-First Graph Traversals Bourotte, Codaline Ducloz, Gwendal Orponen, Pekka Seki, Shinnosuke KLX depth-first search DFS trees k-connectedness tree-width parameterised complexity monadic second-order logic Courcelle’s theorem RNA nanotechnology 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Codaline Bourotte and Gwendal Ducloz and Pekka Orponen and Shinnosuke Seki 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.7 urn:nbn:de:0030-drops-273889 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.7 eng https://creativecommons.org/licenses/by/4.0/legalcode