Abstract
Cycle rank is a depth parameter for digraphs introduced by Eggan in 1963. Gruber and Giannopoulou et al. inquired whether determining if a given digraph has cycle rank at most $w$ is fixed-parameter tractable. We provide algorithms for semi-complete digraphs and digraphs of bounded directed clique-width.
Specifically, given an $n$-vertex semi-complete digraph $G$ and an integer $w$, one can determine whether $G$ has cycle rank at most $w$ in time $\mathrm{O}(9^{(w+1)4^{w+2}} \times n^2)$. The proof is reduced to the bounded directed clique-width case.
Furthermore, for an $n$-vertex digraph $G$ with a directed clique-width $k$-expression and an integer $w$, it can be determined in time $\mathrm{O}(9^{(w+1) 4^k} \times n)$ whether $G$ has cycle rank at most $w$.
Additionally, we consider the $\textsc{Minimum Feedback Arc Set}$ problem on semi-complete digraphs, which can be solved in time $n^{\mathrm{O}(w)}$, where $w$ is the cycle rank of the given semi-complete digraph.
Blogger's Review: This FPT algorithm offers a novel approach to tackling the cycle rank problem for semi-complete digraphs, especially under the constraint of directed clique-width, where the complexity is effectively controlled. This provides a significant theoretical foundation and practical guidance for related research fields, with broad application potential. Future research should focus on optimizing these algorithms for more complex graph structures.