pith. sign in

arxiv: 2606.24675 · v1 · pith:5YSFTD24new · submitted 2026-06-23 · 💻 cs.DM

A Congestion Parameter for Depth-First Graph Traversals

Codaline Bourotte , Gwendal Ducloz , Pekka Orponen , Shinnosuke Seki This is my paper

Pith reviewed 2026-06-25 21:34 UTC · model grok-4.3

classification 💻 cs.DM
keywords KLX numberdepth-first searchback edgestree-widthMSO2 logiclinear-time recognitiongraph congestion parameter
0
0 comments X

The pith

The KLX number, defined as minimum congestion over all depth-first traversals, satisfies tree-width at most KLX plus one and admits linear-time recognition for every fixed bound.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper defines the KLX number of a graph as the minimum, over all its depth-first search traversals, of the maximum number of back edges simultaneously open during the traversal. It proves that this number always exceeds the tree-width by at most one. It further establishes that the property of having KLX number at most any fixed integer k is expressible in monadic second-order logic with edge quantification, which combined with the tree-width bound yields linear-time recognition via Courcelle's theorem. Complete structural characterizations and direct linear-time algorithms are supplied for the cases KLX equal to 0, 1 or 2.

Core claim

The KLX number quantifies the minimum edge congestion of depth-first search traversals of a given graph, defined as the minimum over all DFS traversals of the maximum number of back edges that are simultaneously open during the traversal. Any graph G satisfies TW(G) ≤ KLX(G) + 1. The property KLX ≤ k is MSO2-expressible for every fixed k, implying linear-time recognition. Graphs with KLX numbers 0, 1 or 2 admit full characterizations and linear-time recognition algorithms.

What carries the argument

The KLX number, the minimum over all DFS traversals of the maximum number of simultaneously open back edges.

Load-bearing premise

That an MSO2 formula of size independent of the input graph exists for the property KLX at most k, for each fixed k.

What would settle it

A concrete graph whose tree-width is strictly larger than its KLX number plus one.

read the original abstract

We explore a new graph parameter, the 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 $\mathrm{TW} \le \mathrm{KLX}+1$. Furthermore, we show that the property $\mathrm{KLX} \le k$ is $\mathrm{MSO}_2$-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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 1 minor

Summary. The paper introduces the KLX number of a graph G as the minimum, over all DFS traversals, of the maximum number of back edges simultaneously open at any point during the traversal. It claims full characterizations (with linear-time recognition algorithms) for graphs with KLX number 0, 1 or 2; proves that TW(G) ≤ KLX(G) + 1 for every graph G; and asserts that the property KLX ≤ k is MSO₂-expressible for each fixed k. The latter two results together are said to imply linear-time recognition of bounded-KLX graphs via Courcelle's theorem.

Significance. If the claims hold, the KLX parameter supplies a new, DFS-specific measure of graph congestion that is bounded above by tree-width and admits logical and algorithmic consequences. The explicit characterizations for KLX ≤ 2 and the tree-width inequality are concrete contributions; the MSO₂ route to linear-time recognition for fixed k would be a notable algorithmic corollary if the expressibility argument is fully supplied.

major comments (1)
  1. [MSO₂-expressibility section] The section establishing MSO₂-expressibility of KLX ≤ k: the manuscript states that the property is MSO₂-expressible for fixed k and invokes Courcelle's theorem for the linear-time consequence, yet supplies neither an explicit MSO₂ sentence nor a construction showing how the existence of a DFS spanning tree together with a bounded-congestion condition on simultaneously open back edges can be expressed using only vertex-set and edge-set quantifiers. Because MSO₂ cannot directly quantify arbitrary total orders or traversal sequences, this step is load-bearing for the recognition claim and requires a detailed argument or formula.
minor comments (1)
  1. [Abstract] The abstract states that full characterizations have been proved but contains no proof sketches or counter-example verification; moving a brief outline of the KLX = 0,1,2 cases into the abstract or introduction would improve readability.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the detailed review and for highlighting the need for a more explicit treatment of the MSO₂-expressibility claim. We address the single major comment below.

read point-by-point responses

  1. Referee: [MSO₂-expressibility section] The section establishing MSO₂-expressibility of KLX ≤ k: the manuscript states that the property is MSO₂-expressible for fixed k and invokes Courcelle's theorem for the linear-time consequence, yet supplies neither an explicit MSO₂ sentence nor a construction showing how the existence of a DFS spanning tree together with a bounded-congestion condition on simultaneously open back edges can be expressed using only vertex-set and edge-set quantifiers. Because MSO₂ cannot directly quantify arbitrary total orders or traversal sequences, this step is load-bearing for the recognition claim and requires a detailed argument or formula.

    Authors: We agree that the current manuscript asserts MSO₂-expressibility at a high level without supplying an explicit formula or construction. In the revision we will expand the relevant section with a detailed argument. The construction proceeds by first expressing (in MSO₂) the existence of a spanning tree T that admits a depth-first ordering; this can be done by quantifying over the set of tree edges and using the fixed bound k to encode the possible states of open back edges via auxiliary vertex sets that track the at-most-k “live” back edges at each step. Because k is fixed, the congestion condition becomes a finite collection of local checks on edge incidences and ancestor-descendant relations (both MSO₂-definable), avoiding the need to quantify over arbitrary linear orders. We will include the resulting MSO₂ sentence (or a clear inductive description of its clauses) together with a proof that it correctly captures KLX ≤ k. revision: yes

Circularity Check

0 steps flagged

No circularity: KLX defined directly; TW bound and MSO2 claim are independent theorems

full rationale

The KLX number is defined explicitly as the minimum, over all DFS traversals, of the maximum number of simultaneously open back edges. The TW ≤ KLX + 1 inequality and the MSO2-expressibility of KLX ≤ k for fixed k are stated as separate results (with the latter combined with the tree-width bound to obtain linear-time recognition). No step reduces a claimed theorem to the definition by construction, no fitted parameter is relabeled as a prediction, and no load-bearing premise rests on a self-citation chain. The derivation chain is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The paper rests on the standard definitions of graphs, depth-first search, back edges, tree-width, and monadic second-order logic; the KLX number itself is the sole invented entity and is defined rather than postulated with external evidence.

axioms (1)
  • standard math Standard definitions and properties of undirected graphs, DFS traversals, back edges, tree-width, and MSO2 logic hold.
    All results are built on these background notions from graph theory and logic.
invented entities (1)
  • KLX number no independent evidence
    purpose: Quantifies the minimum over DFS traversals of the maximum number of simultaneously open back edges.
    Newly defined parameter; no independent external evidence or falsifiable prediction outside the definition is supplied in the abstract.

pith-pipeline@v0.9.1-grok · 5729 in / 1455 out tokens · 27835 ms · 2026-06-25T21:34:04.717800+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 16 canonical work pages

  1. [1]

    2016 , issn =

    Proper orientation of cacti , journal =. 2016 , issn =. doi:https://doi.org/10.1016/j.tcs.2016.05.016 , author =

    work page doi:10.1016/j.tcs.2016.05.016 2016

  2. [2]

    Approximation Algorithms for Treewidth, Pathwidth, and Treedepth---A Short Survey

    Bodlaender, Hans L. Approximation Algorithms for Treewidth, Pathwidth, and Treedepth---A Short Survey. Graph-Theoretic Concepts in Computer Science. 2025

    2025

  3. [3]

    , title =

    Bodlaender, Hans L. , title =. SIAM Journal on Computing , volume =. 1996 , doi =

    1996

  4. [4]

    Algorithmica , author =

    Parameterized complexity of the spanning tree congestion problem , volume =. Algorithmica , author =. 2012 , pages =. doi:10.1007/s00453-011-9565-7 , number =

    work page doi:10.1007/s00453-011-9565-7 2012

  5. [5]

    Bollobás, Béla , year =. Modern. doi:https://doi.org/10.1007/978-1-4612-0619-4 , publisher =

    work page doi:10.1007/978-1-4612-0619-4

  6. [6]

    Graph Structure and Monadic Second-Order Logic

    Bruno Courcelle and Joost Engelfriet. Graph Structure and Monadic Second-Order Logic. Universidade do Porto

  7. [7]

    Information and Computation , volume =

    The monadic second-order logic of graphs. Information and Computation , volume =. 1990 , issn =. doi:10.1016/0890-5401(90)90043-H , author =

    work page doi:10.1016/0890-5401(90)90043-h 1990

  8. [8]

    2012 , isbn =

    Courcelle, Bruno and Engelfriet, Joost , title =. 2012 , isbn =

    2012

  9. [9]

    Diestel, Reinhard , year =. Graph. doi:10.1007/978-3-662-70107-2 , number =

    work page doi:10.1007/978-3-662-70107-2

  10. [10]

    and Kuzyk, Anton and Orponen, Pekka , title =

    Elonen, Antti and Natarajan, Ashwin Karthick and Kawamata, Ibuki and Oesinghaus, Lukas and Mohammed, Abdulmelik and Seitsonen, Jani and Suzuki, Yuki and Simmel, Friedrich C. and Kuzyk, Anton and Orponen, Pekka , title =. ACS Nano , volume =. 2022 , doi =

    2022

  11. [11]

    and Andersen, Ebbe S

    Geary, Cody W. and Andersen, Ebbe S. , editor =. Design principles for single-stranded. 2014 , pages =. doi:10.1007/978-3-319-11295-4_1 , booktitle =

    work page doi:10.1007/978-3-319-11295-4_1 2014

  12. [12]

    and Meunier, Pierre-Etienne and Schabanel, Nicolas and Seki, Shinnosuke , editor =

    Geary, Cody W. and Meunier, Pierre-Etienne and Schabanel, Nicolas and Seki, Shinnosuke , editor =. Programming biomolecules that fold greedily during transcription , volume =. 2016 , pages =. doi:10.4230/LIPIcs.MFCS.2016.43 , booktitle =

    work page doi:10.4230/lipics.mfcs.2016.43 2016

  13. [13]

    Science , author =

    A single-stranded architecture for cotranscriptional folding of. Science , author =. 2014 , pages =. doi:10.1126/science.1253920 , number =

    work page doi:10.1126/science.1253920 2014

  14. [14]

    Nano Letters , author =

    Self-assembling. Nano Letters , author =. 2011 , pages =. doi:10.1021/nl104271s , number =

    work page doi:10.1021/nl104271s 2011

  15. [15]

    Algorithm 447: Efficient algorithms for graph manipulation.Communications of the ACM, 16(6):372–378, 1973

    Hopcroft, John and Tarjan, Robert , title =. 1973 , issue_date =. doi:10.1145/362248.362272 , journal =

    work page doi:10.1145/362248.362272 1973

  16. [16]

    1993 , issn =

    Tree-width, path-width, and cutwidth , journal =. 1993 , issn =. doi:https://doi.org/10.1016/0166-218X(93)90171-J , author =

    work page doi:10.1016/0166-218x(93)90171-j 1993

  17. [17]

    Algorithmica , author =

    Better hardness results for the minimum spanning tree congestion problem , volume =. Algorithmica , author =. 2025 , pages =. doi:10.1007/s00453-024-01278-5 , number =

    work page doi:10.1007/s00453-024-01278-5 2025

  18. [18]

    Algorithmic Design of Cotranscriptionally Folding 2D RNA Origami Structures

    Mohammed, Abdulmelik and Orponen, Pekka and Pai, Sachith. Algorithmic Design of Cotranscriptionally Folding 2D RNA Origami Structures. Unconventional Computation and Natural Computation. 2018

    2018

  19. [19]

    Secondary structure design for cotranscriptional

    Orponen, Pekka and Seki, Shinnosuke and Elonen, Antti , editor =. Secondary structure design for cotranscriptional. 2025 , pages =. doi:10.4230/LIPIcs.DNA.31.6 , booktitle =

    work page doi:10.4230/lipics.dna.31.6 2025

  20. [20]

    Discrete Mathematics , author =

    Minimal congestion trees , volume =. Discrete Mathematics , author =. 2004 , pages =. doi:10.1016/j.disc.2004.02.009 , number =

    work page doi:10.1016/j.disc.2004.02.009 2004

  21. [21]

    Graph minors. III. Planar tree-width , journal =. 1984 , issn =. doi:https://doi.org/10.1016/0095-8956(84)90013-3 , author =

    work page doi:10.1016/0095-8956(84)90013-3 1984

  22. [22]

    On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves

    Sam, Emmanuel and Fellows, Michael and Rosamond, Frances and Golovach, Petr A. On the Parameterized Complexity of the Structure of Lineal Topologies (Depth-First Spanning Trees) of Finite Graphs: The Number of Leaves. Algorithms and Complexity. 2023. doi:10.1007/978-3-031-30448-4_25

    work page doi:10.1007/978-3-031-30448-4_25 2023

  23. [23]

    2024 , doi =

    Current Opinion in Chemical Biology , volume =. 2024 , doi =

    2024