An FPT algorithm for cycle rank on semi-complete digraphs

Abstract

Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber (DMTCS 2012) and Giannopoulou, Hunter, and Thilikos (DAM 2012) asked whether the problem of determining if a given digraph has cycle rank at most w is fixed-parameter tractable parameterized by w. We provide such algorithms for semi-complete digraphs, and for digraphs of bounded directed clique-width. Specifically, we show that given an n-vertex semi-complete digraph~G and an integer w, one can in time 2^{𝒪((w+1)4^w)} n² determine whether G has cycle rank at most~w. The proof is reduced to the case of bounded directed clique-width, and we then show that given an n-vertex digraph G with a directed clique-width k-expression and an integer w, one can in time 2^{𝒪((w+1)4^k)}n determine whether G has cycle rank at most w. Additionally, we consider the \textsc{Minimum Feedback Arc Set} problem on semi-complete digraphs, and show that it can be solved in time n^𝒪(w), when a cycle rank decomposition of depth w≥ 1 is given.

Period Piece: NEXPTIME-complete problems on digraphs via Boolean network dynamics
Florian Bridoux, Maximilien Gadouleau, David C. Kutner +1
arXiv12 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
A complete classification for n-species Lotka-Volterra stably dissipative systems based on a generalized AHU algorithm
Yajia Du, Zhengyi Lu, Jinya Xu +1
arXiv1 Nov 2026PreprintCC BY 4.0Full textDynamical systemsarXiv
Waring rank of certain complete intersection forms
Meghana Bhat, Enrico Carlini, Shreedevi K. Masuti +1
arXiv13 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv
Four-Dimensional Semi-Homogeneous Convex Cones: A Complete Classification
Amir Valiakhmetov, Ewsey Obzherin, Alexey Chernov +1
arXiv1 Nov 2026PreprintCC BY 4.0Full textGeometry & topologyarXiv
The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
G. Arunkumar, Puja Samanta
arXiv13 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeX RIS

BibTeX

@misc{kim2026algorithm,
  title = {{An FPT algorithm for cycle rank on semi-complete digraphs}},
  author = {Seokbeom Kim and O-joung Kwon and Myounghwan Lee},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2606.29336},
  eprint = {2606.29336},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.29336},
}

RIS

TY  - UNPB
TI  - An FPT algorithm for cycle rank on semi-complete digraphs
AU  - Seokbeom Kim
AU  - O-joung Kwon
AU  - Myounghwan Lee
PY  - 2026
DA  - 2026/09/23
PB  - arXiv
DO  - 10.48550/arxiv.2606.29336
UR  - https://arxiv.org/abs/2606.29336
AB  - Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber (DMTCS 2012) and Giannopoulou, Hunter, and Thilikos (DAM 2012) asked whether the problem of determining if a given digraph has cycle rank at most w is fixed-parameter tractable parameterized by w. We provide such algorithms for semi-complete digraphs, and for digraphs of bounded directed clique-width. Specifically, we show that given an n-vertex semi-complete digraph~G and an integer w, one can in time 2^𝒪((w+1)4^w) n^2 determine whether G has cycle rank at most~w. The proof is reduced to the case of bounded directed clique-width, and we then show that given an n-vertex digraph G with a directed clique-width k-expression and an integer w, one can in time 2^𝒪((w+1)4^k)n determine whether G has cycle rank at most w. Additionally, we consider the \textsc{Minimum Feedback Arc Set} problem on semi-complete digraphs, and show that it can be solved in time n^𝒪(w), when a cycle rank decomposition of depth w≥ 1 is given.
ER  -

Abstract

Related

Cite