Skip to content
DraconiticResearch
Search Sources API
197,788 studies31 sourcesUpdated 16 min ago
PreprintCC BY-NC-ND 4.0HAL

Stable Set Reconfiguration in Dense Digraphs

  • Sarah Houdaigoui
  • Nacim Oijid
  • Matthieu Petiteau
  • Alexandre Vigny
Open at sourcePDFDOICite

Abstract

In a directed graph, a stable (or acyclic) set is a set which does not induce a directed cycle. Given a directed graph and two acyclic sets of the same size, the Acyclic-Set-Reconfiguration with Directed Token Sliding (ASR) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while maintaining acyclicity during the transformation. In this work, we present a study of the complexity of ASR and provide an FPT algorithm for semi-complete digraphs, when parametrized by the size of the sets being reconfigured, the directed pathwidth (or equivalently, the directed treewidth) of the instance, and a newly introduced parameter called the iteration of the reconfiguration sequence. To the best of our knowledge, the reconfiguration of stable sets has only been studied on undirected graphs, or (more recently) on sparse directed graphs.

Related

  1. Large corank of dense random regular digraphs
    Huaijin Liang, Kexin Yu, Tingzhou Yu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  2. Highly connected uniquely k-linked digraphs
    Jørgen Bang-Jensen
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. s-quasi-transitive weakly distance-regular digraphs
    Shuang Li, Yuefeng Yang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Randomized Borel (2d+1)-coloring of digraphs
    Anton Bernshteyn, Edward Hou, Forte Shinko +1
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsLogic & foundationsarXiv
  5. Erdős-Sós for digraphs
    Dhruv Mubayi, Jacques Verstraete
    arXivPreprintCC0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{houdaigoui2026stable,
  title = {{Stable Set Reconfiguration in Dense Digraphs}},
  author = {Sarah Houdaigoui and Nacim Oijid and Matthieu Petiteau and Alexandre Vigny},
  howpublished = {HAL},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.32402},
  eprint = {2610.32402},
  archivePrefix = {arXiv},
  url = {https://hal.science/hal-05838787v1},
  note = {CC BY-NC-ND 4.0},
}
RIS
TY  - UNPB
TI  - Stable Set Reconfiguration in Dense Digraphs
AU  - Sarah Houdaigoui
AU  - Nacim Oijid
AU  - Matthieu Petiteau
AU  - Alexandre Vigny
PY  - 2026
DA  - 2026/10/23
PB  - HAL
DO  - 10.48550/arxiv.2610.32402
UR  - https://hal.science/hal-05838787v1
AB  - In a directed graph, a stable (or acyclic) set is a set which does not induce a directed cycle. Given a directed graph and two acyclic sets of the same size, the Acyclic-Set-Reconfiguration with Directed Token Sliding (ASR) problem asks whether one can, by iteratively replacing a vertex by an adjacent one, transform the first set into the second one, while maintaining acyclicity during the transformation. In this work, we present a study of the complexity of ASR and provide an FPT algorithm for semi-complete digraphs, when parametrized by the size of the sets being reconfigured, the directed pathwidth (or equivalently, the directed treewidth) of the instance, and a newly introduced parameter called the iteration of the reconfiguration sequence. To the best of our knowledge, the reconfiguration of stable sets has only been studied on undirected graphs, or (more recently) on sparse directed graphs.
ER  -