Search Results

Documents authored by Ducloz, Gwendal

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}
}
Document
DOI: 10.4230/LIPIcs.DNA.32.4
PENSim: A Toolkit for PEN-DNA Systems

Authors: Gwendal Ducloz and Nicolas Schabanel

Published in: LIPIcs, Volume 387, 32nd International Conference on DNA Computing and Molecular Programming (DNA 32) (2026)

Abstract
The PEN-DNA toolbox has emerged as a versatile framework for implementing chemical reaction networks with DNA and enzymes, enabling applications ranging from molecular sensing to neural computation. A simulation tool, DACCAD, has provided a standardized approach for translating network schematics into dynamical models, facilitating in silico design and validation. However, the evolution of the PEN-DNA toolbox - particularly the transition from inhibitor-based regulation to drain-template-based inactivation - introduces mechanisms that are only partially captured by existing simulation frameworks, limiting the ability to reliably simulate and design recent PEN-DNA systems. In this context, we introduce PENSim, a simulation package that aims to realign computational modeling with current experimental practices. By extending the repertoire of simulated reactions and incorporating thermodynamic dependencies into kinetic rate calculations via NUPACK, PENSim enables a more faithful representation of modern PEN-DNA systems. In particular, accounting for thermodynamic effects is essential for accurately modeling inactivation via drain templates. PENSim is validated through qualitative reproduction of existing experimental results, including inactivation-driven bistability, microRNA detection circuits, and linear classifiers based on neural networks. By bridging legacy modeling approaches with recent experimental advances, PENSim provides a step toward more realistic and flexible in silico design of systems based on the PEN-DNA toolbox.
Cite as

Gwendal Ducloz and Nicolas Schabanel. PENSim: A Toolkit for PEN-DNA Systems. In 32nd International Conference on DNA Computing and Molecular Programming (DNA 32). Leibniz International Proceedings in Informatics (LIPIcs), Volume 387, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ducloz_et_al:LIPIcs.DNA.32.4,
  author =	{Ducloz, Gwendal and Schabanel, Nicolas},
  title =	{{PENSim: A Toolkit for PEN-DNA Systems}},
  booktitle =	{32nd International Conference on DNA Computing and Molecular Programming (DNA 32)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-444-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{387},
  editor =	{Scalise, Dominic and Schweller, Robert},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.32.4},
  URN =		{urn:nbn:de:0030-drops-267743},
  doi =		{10.4230/LIPIcs.DNA.32.4},
  annote =	{Keywords: PEN-DNA toolbox, DNA circuit simulation, DNA reaction kinetics, Enzymatic DNA reaction kinetics}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.1
Algorithmic Hardness of the Partition Function for Nucleic Acid Strands

Authors: Gwendal Ducloz, Ahmed Shalaby, and Damien Woods

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
To understand and engineer biological and artificial nucleic acid systems, algorithms are employed for prediction of secondary structures at thermodynamic equilibrium. Dynamic programming algorithms are used to compute the most favoured, or Minimum Free Energy (MFE), structure, and the Partition Function (PF) - a tool for assigning a probability to any structure. However, in some situations, such as when there are large numbers of strands, or pseudoknotted systems, NP-hardness results show that such algorithms are unlikely, but only for MFE. Curiously, algorithmic hardness results were not shown for PF, leaving two open questions on the complexity of PF for multiple strands and single strands with pseudoknots. The challenge is that while the MFE problem cares only about one, or a few structures, PF is a summation over the entire secondary structure space, giving theorists the vibe that computing PF should not only be as hard as MFE, but should be even harder. We answer both questions. First, we show that computing PF is #P-hard for systems with an unbounded number of strands, answering a question of Condon Hajiaghayi, and Thachuk [DNA27]. Second, for even a single strand, but allowing pseudoknots, we find that PF is #P-hard. Our proof relies on a novel magnification trick that leads to a tightly-woven set of reductions between five key thermodynamic problems: MFE, PF, their decision versions, and #SSEL that counts structures of a given energy. Our reductions show these five problems are fundamentally related for any energy model amenable to magnification. That general classification clarifies the mathematical landscape of nucleic acid energy models and yields several open questions.
Cite as

Gwendal Ducloz, Ahmed Shalaby, and Damien Woods. Algorithmic Hardness of the Partition Function for Nucleic Acid Strands. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ducloz_et_al:LIPIcs.DNA.31.1,
  author =	{Ducloz, Gwendal and Shalaby, Ahmed and Woods, Damien},
  title =	{{Algorithmic Hardness of the Partition Function for Nucleic Acid Strands}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{1:1--1:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.1},
  URN =		{urn:nbn:de:0030-drops-238504},
  doi =		{10.4230/LIPIcs.DNA.31.1},
  annote =	{Keywords: Partition function, minimum free energy, nucleic acid, DNA, RNA, secondary structure, computational complexity, #P-hardness}
}

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