A Congestion Parameter for Depth-First Graph Traversals

Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, Shinnosuke Seki · 2026

Read A Congestion Parameter for Depth-First Graph Traversals by Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, Shinnosuke Seki (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24675.txt.

Introduction

Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, and Shinnosuke Seki introduce a new graph parameter called the KLX number. It measures congestion during depth first search, the classic method that dives along one path before backtracking. For a given graph, the KLX number is the smallest possible worst case count of back edges open at once. The idea grew out of a problem in RNA nanostructure design.

Bourotte and colleagues fully characterise graphs with KLX number zero, one, and two. They give linear time recognition algorithms for those cases. They also bound tree width by the KLX number plus one. For any fixed bound k, the property of having KLX number at most k can be expressed in monadic second order logic. Combined with the tree width bound, that yields linear time tests for every constant k. The parameter thus ties a search order notion to classic width measures.

Catalog record

CREATORCodaline Bourotte, Gwendal Ducloz, Pekka Orponen, Shinnosuke Seki
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE80 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24675

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Congestion Parameter for Depth-First Graph Traversals Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, Shinnosuke Seki 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 \mathrm{TW}\leq\mathrm{KLX}+1 . Furthermore, we show that the property KLX ≤ k \mathrm{KLX}\leq k is MSO 2 \mathrm{MSO}_{2} -expressible for every fixed k k . Combined with the tree-width bound, this result implies that determining whether a graph has KLX number at most k k can be achieved in linear time for any constant k k . École Normale Supérieure de Lyon, [email protected]://orcid.org/0009-0009-3488-0425Work supported in part by the grant “Bourse Région Mobilité Internationale Etudiants de la région Auvergne-Rhône-Alpes” and by Kubota Information Technology École Normale Supérieure de Lyon, LIP (UMR 5668, Équipe MC2), [email protected]://orcid.org/0009-0002-2015-267XWork supported in part by the French government under the “France 2030” programme ANR-24-RRII-0001, ANR-22-CE09-0034, and ANR-22-CE45-0020. Aalto University, [email protected]://orcid.org/0000-0002-0417-2104 University of Electro-Communications, [email protected]://orcid.org/0000-0002-0276-3322Work supported in part by Ambition Internationale de la Région Auvergne-Rhône-Alpes No. 00284230-1 and by the Aalto Science Institute visiting researcher programme. {CCSXML} ¡ccs2012¿ ¡concept¿ ¡concept_id¿10010405.10010444.10010087¡/concept_id¿ ¡concept_desc¿Applied computing Computational biology¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10002950.10003624.10003633.10010917¡/concept_id¿ ¡concept_desc¿Mathematics of computing Graph algorithms¡/concept_desc¿ ¡concept_significance¿500¡/concept_significance¿ ¡/concept¿ ¡concept¿ ¡concept_id¿10003752.10003809.10010052.10010053¡/concept_id¿ ¡concept_desc¿Theory of computation Fixed parameter tractability¡/concept_desc¿ ¡concept_significance¿300¡/concept_significance¿ ¡/concept¿ ¡/ccs2012¿ A major part of this work was done during an internship of C.B. at the University of Electro-Communications, Japan. Further work was pursued during a visit of S.S. and G.D. to Aalto University, Finland, and during an internship of G.D. at the University of Electro-Communications. \declaretheorem [name=Algorithm,numberwithin=section]restatablealg ccs Mathematics of computing Graph algorithms ccs Theory of computation Fixed parameter tractability ccs Applied computing Computational biology keywords KLX, depth-first search, DFS trees, k -connectedness, tree-width, parameterised complexity, monadic second-order logic, Courcelle’s theorem, RNA nanotechnology † † runningauthor: C. Bourotte et al. † † copyright: Codaline Bourotte, Gwendal Ducloz, Pekka Orponen, and Shinnosuke Seki † † editors: Michal Koucký and Daniela Petrişan † † event-title: 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) † † event-shorttitle: MFCS 2026 † † event-acronym: MFCS † † year: 2026 † † event-date: August 24–28, 2026 † † event-location: Paris, France † † series-volume: 386 † † articleno: 1 1 Introduction 1.1 Background In this paper we investigate the minimum “congestion” of depth-first graph traversals, in the sense of how many back edges are simultaneously open (discovered but not concluded) at any point during the traversal. This concept is analogous to the notion of spanning tree congestion introduced by Ostrovskii [ 12 ] , but is specific to ordered DFS trees, and addresses the dynamic traversal process rather than the static DFS tree. Our interest in this concept was spurred by a practical problem in RNA nanotechnology [ 14 ] , viz. minimising the number of kissing-loop connector motifs in the algorithmic design of co-transcriptionally folding RNA wireframe nanostructures [ 6 , 7 , 11 ] . {subfigure} [t]0.2 \subcaption {subfigure} [t]0.2 \subcaption {subfigure} [t]0.2 \subcaption {subfigure} [t]0.2 \subcaption Figure 1: A spanning-tree based design scheme for RNA wireframe nanostructures. (a) Targeted wireframe model. (b) A spanning tree and strand routing of the wireframe graph. (c) Routing-based helical and kissing-loop pairings. (d) Helix-level model. (Adapted with permission from [ 6 ] .) In this design task, one starts with a graph model G that represents the targeted wireframe nanostructure ( \cref fig:rna-design(a)), and then designs an initial route for the RNA strand by a traversal around some spanning tree T of G (blue curve in \cref fig:rna-design(b)). This establishes an RNA base-pairing scheme for creating the tree T , but omits the co-tree edges (dashed red lines in \cref fig:rna-design(b)). These are grafted to the design by extending the strand routing by two half-edges from both end-vertices of each co-tree edge, and terminating these extensions in “kissing loop” (KL) pairs with pairwise matching base sequences ( \cref fig:rna-design(c)). \cref fig:rna-design(d) presents a helix-level model of the resulting nanostructure. In nature, RNA is transcribed from a DNA template by a polymerase enzyme molecule and folds co-transcriptionally , that is, already while being transcribed. This opens up the possibility of reusing the KL base-pair sequences, because once a transcribed KL pair has closed, there is no longer a risk of mispairings from introducing another copy of the same sequence pair. This opportunity is potentially significant for large structures and motivates interest in cotranscriptional designs with a minimum number of simultaneously open KL pairs, that is, graph traversals with a minimum number of simultaneously open co-tree edges . Co-transcriptional folding also has a downside: if the scheduling of the KL pairings relative to the helix transcriptions is bad, it is possible that the polymerase molecule becomes “trapped” by a KL pair that closes too early, and the winding of the downstream helices cannot be completed [ 8 ] . Surprisingly, this kinetic folding trap can be decisively avoided in wireframe designs if and only if the spanning tree used for routing is a DFS tree [ 11 ] . Accordingly, and following [ 11 ] , we define the \mathrm{KLX} (“kissing loop crossing”) number of a graph G as the minimum number of simultaneously open back edges in any DFS traversal of G , and aim to characterise and recognise those graphs that can be constituted with a small \mathrm{KLX} number. Even though this parameter thus has an application-driven origin, it connects to the broad literature on edge congestion problems, e.g. [ 2 , 10 , 12 ] . 1.2 Structure of the paper After introducing some preliminaries in \cref sec:preliminaries, we provide characterisations of graphs with small KLX values in \cref sec:klx-leq-2. Specifically, we show that: graphs with \mathrm{KLX}\leq 1 are cactus graphs, and graphs with \mathrm{KLX}\leq 2 admit an explicit, linear-time decidable characterisation. Computing the \mathrm{KLX} value is known to be NP-hard [ 11 ] , but in \cref sec:fpt-courcelle we establish the existence of a linear-time fixed-parameter tractable (FPT) algorithm to test whether \mathrm{KLX}\leq k for any constant k . Our approach is based on Courcelle’s Theorem [ 5 ] , and consists of two key steps: we prove that the tree-width \mathrm{TW} of any graph satisfies \mathrm{TW}\leq\mathrm{KLX}+1 , and we demonstrate that the condition \mathrm{KLX}\leq k is \mathrm{MSO}_{2} -expressible. All the proofs that have been abridged or omitted in the main paper are provided in the Appendix. 2 Preliminaries All graphs G=(V,E) considered in this article are connected and simple. We denote by \deg(x) the degree of a vertex x\in V , and by \delta(G) and \Delta(G) the minimum and maximum degrees of vertices in G . For S\subseteq V , we denote by G[S] the subgraph of G induced by the vertices in S . We use the notation |C| for the length

Read the complete text