{"id":"arxiv/2606.29336","url":"https://arxiv.org/abs/2606.29336","tags":["cs.DS","math.CO"],"score":0,"title":"An FPT algorithm for cycle rank on semi-complete digraphs","domain":"cs.DS","source":"arxiv","authors":["Seokbeom Kim","O-joung Kwon","Myounghwan Lee"],"reviews":0,"subject":"cs.DS","summary":"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^{\\mathcal{O}((w+1)4^{w})} n^2$ determine whether $G$ has cycle rank at most~$w$. The proof is…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-28","reactions":{}}