Pith. sign in

REVIEW 39 references

An FPT algorithm for cycle rank on semi-complete digraphs

T0 review · reviewed 2026-06-30 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Cycle rank at most w is decidable in time O(9^{(w+1)4^{w+2}} n²) on n-vertex semi-complete digraphs.

desk verdict Resolves the 2012 open question with explicit FPT algorithms for cycle rank on semi-complete digraphs by reducing to directed clique-width. read the letter →

arxiv 2606.29336 v1 pith:HXJ52RNK submitted 2026-06-28 cs.DS math.CO

Seokbeom Kim , O-joung Kwon , Myounghwan Lee This is my paper
classification cs.DSmath.CO
keywords cycleranksemi-completedigraphsfixed-parametertractabilitydirectedclique-widthdynamicprogrammingfeedbackarcset
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes that deciding whether the cycle rank of a semi-complete digraph is at most a given w is fixed-parameter tractable when parameterized by w. It does this by reducing the input to an equivalent instance on a digraph of directed clique-width bounded by a function of w, then solving via dynamic programming on a directed clique-width expression. A reader would care because cycle rank is a classical 1963 parameter whose fixed-parameter tractability was open even on this dense class of digraphs. The same approach yields a linear-time algorithm when the directed clique-width expression is supplied, and an n^{O(w)} algorithm for Minimum Feedback Arc Set on semi-complete digraphs parameterized by their cycle rank.

What carries the argument

Dynamic programming over a directed clique-width k-expression that tracks whether cycle rank is at most w.

What would settle it

A semi-complete digraph on at most ten vertices whose cycle rank is known by exhaustive enumeration but on which the claimed algorithm returns the opposite yes/no answer for some small w.

Watch

Extended reading notes

Core claim

Given an n-vertex semi-complete digraph G and integer w, one can decide in time O(9^{(w+1)4^{w+2}} · n²) whether G has cycle rank at most w. The proof reduces the problem to the bounded directed clique-width case; when a directed clique-width k-expression is given, the same decision can be made in time O(9^{(w+1)4^k} · n). Minimum Feedback Arc Set on semi-complete digraphs can additionally be solved in n^{O(w)} time when w is the cycle rank of the input.

Load-bearing premise

The dynamic programming correctly computes cycle rank from the directed clique-width expression and the reduction from arbitrary semi-complete digraphs produces an equivalent instance whose directed clique-width is bounded by a function of w while preserving whether cycle rank is at most w.

Editorial extensions

If this is right

  • Cycle rank at most w is fixed-parameter tractable on semi-complete digraphs.
  • Minimum Feedback Arc Set is solvable in n^{O(w)} time on semi-complete digraphs when parameterized by cycle rank.
  • Cycle rank at most w is fixed-parameter tractable on any digraph supplied with a directed clique-width k-expression.
  • The same dynamic programming states decide the problem once the reduction to bounded directed clique-width is performed.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • An explicit polynomial-time construction of the bounded-width expression would immediately give an FPT algorithm that also outputs a certificate for the cycle rank.
  • The reduction technique may extend to other digraph width parameters that are preserved under the semi-complete property.
  • The approach leaves open whether an FPT algorithm exists for cycle rank on arbitrary digraphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

0 major / 0 minor

Summary. The paper claims an FPT algorithm for deciding if the cycle rank of an n-vertex semi-complete digraph is at most w, running in time O(9^{(w+1)4^{w+2}} · n²). This is achieved by a parameter-preserving reduction to digraphs of bounded directed clique-width, followed by dynamic programming on a directed clique-width k-expression that runs in time O(9^{(w+1)4^k} · n). An additional result is an n^{O(w)}-time algorithm for Minimum Feedback Arc Set on semi-complete digraphs parameterized by cycle rank w.

Significance. If the claims hold, this resolves the open question posed by Gruber (2012) and Giannopoulou et al. (2012) on the FPT status of cycle rank parameterized by w for semi-complete digraphs. The explicit reduction to directed clique-width (with parameter bound) and the DP construction on clique-width expressions are concrete algorithmic contributions; the manuscript ships an explicit (though doubly exponential) running-time bound derived directly from the operations.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for recommending acceptance. The report accurately summarizes our main results and their significance in resolving the open question from Gruber (2012) and Giannopoulou et al. (2012).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; explicit algorithmic construction

full rationale

The paper derives an FPT algorithm via an explicit parameter-preserving reduction from semi-complete digraphs to directed clique-width expressions of width bounded by a function of w, followed by dynamic programming whose states and recurrences are constructed directly from the clique-width operations to track cycle rank. All time bounds (O(9^{(w+1)4^{w+2}} n²) and O(9^{(w+1)4^k} n)) follow from enumerating the finite number of DP states without fitted constants, self-definitional loops, or load-bearing self-citations. The central claim is self-contained against external benchmarks and does not reduce any claimed result to its own inputs by construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

The result rests on the standard definitions of cycle rank, semi-complete digraphs, and directed clique-width from the literature cited in the abstract, together with the correctness of dynamic programming on clique-width expressions; no new free parameters, ad-hoc axioms, or invented entities are introduced.

assumptions (1)
  • standard math Cycle rank, semi-complete digraphs, and directed clique-width are defined as in the 1963 Eggan paper and the 2012 Gruber / Giannopoulou et al. references.
    The algorithm statements presuppose these established notions without re-deriving them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An FPT algorithm for cycle rank on semi-complete digraphs." pith.science (2026). https://pith.science/paper/HXJ52RNK

@misc{pith2026260629336,
  author       = {Pith},
  title        = {Pith review of: An FPT algorithm for cycle rank on semi-complete digraphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/HXJ52RNK}},
  note         = {Machine review of arXiv:2606.29336}
}
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 $\mathcal{O}(9^{(w+1)4^{w+2}} \cdot 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 $\mathcal{O}(9^{(w+1) 4^k} \cdot 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^{\mathcal{O}(w)}$, where $w$ is the cycle rank of the given semi-complete digraph.

Figures

Figures reproduced from arXiv: 2606.29336 by the authors.

Figure 1
Figure 1. When adding all edges from vertices of label [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. An example describing why we need to store the in-se [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. For each vertex vi , let lab(vi) = i. The digraph is obtained by applying the operation αb,c to the base digraph consisting of the black edges. (The added edge (vb, vc) is drawn in red.) Let f be the guessed ranking function. Then for m = 2, we have M′ [{c}, {c, d}; 2] = 1 and all the other values are 0. We compute the reachability sets R ↓ b (2) = {a, b} and R↑ c (2) = {c, d}. Thus, for A′ = {c} and B′ = {c, d}, we… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The set At of proper ancestors of a node t and the vertex set St of the subtree Tt rooted at t. on V (G), we say an edge (vi , vj ) ∈ E(G) is a σ-backedge if i > j. Then for every linear order σ on V (G), the set of σ-backedges is always a feedback arc set of G. Moreov…

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

39 extracted references · 2 canonical work pages

  1. [1]

    Ranking tournaments

    Noga Alon. Ranking tournaments. SIAM J. Discrete Math. , 20(1):137–142, 2006

    2006

  2. [2]

    Fast F A ST

    Noga Alon, Daniel Lokshtanov, and Saket Saurabh. Fast F A ST. In Automata, languages and programming. Part I , volume 5555 of Lecture Notes in Comput. Sci. , pages 49–58. Springer, Berlin, 2009

    2009

  3. [3]

    Tournaments a nd semicomplete digraphs

    Jørgen Bang-Jensen and Fr´ ed´ eric Havet. Tournaments a nd semicomplete digraphs. In Jørgen Bang-Jensen and Gregory Gutin, editors, Classes of Directed Graphs , pages 35–124, Cham,

  4. [4]

    Springer International Publishing

  5. [5]

    A polynomial algorithm for the 2-path problem for semicomplete digraphs

    Jørgen Bang-Jensen and Carsten Thomassen. A polynomial algorithm for the 2-path problem for semicomplete digraphs. SIAM J. Discrete Math. , 5(3):366–376, 1992

    1992

  6. [6]

    DAG-width and par- ity games

    Dietmar Berwanger, Anuj Dawar, Paul Hunter, and Stephan Kreutzer. DAG-width and par- ity games. In STACS 2006, volume 3884 of Lecture Notes in Comput. Sci. , pages 524–536. Springer, Berlin, 2006. 21

    2006

  7. [7]

    The minimum feedback arc set problem is NP-hard for tournaments

    Pierre Charbit, St´ ephan Thomass´ e, and Anders Yeo. The minimum feedback arc set problem is NP-hard for tournaments. Combin. Probab. Comput. , 16(1):1–4, 2007

    2007

  8. [8]

    A fixed-parameter algorithm for the directed feedback vertex set problem

    Jianer Chen, Yang Liu, Songjian Lu, Barry O’Sullivan, an d Igor Razgon. A fixed-parameter algorithm for the directed feedback vertex set problem. J. ACM , 55(5):Art. 21, 19, 2008

    2008

Show all 39 references
  1. [9]

    Computing slater rankings using simi larities among candidates

    Vincent Conitzer. Computing slater rankings using simi larities among candidates. In AAAI, volume 6, pages 613–619, 2006

    2006

  2. [10]

    Makowsky, and Udi Rotics

    Bruno Courcelle, Johann A. Makowsky, and Udi Rotics. Lin ear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Syst. , 33(2):125–150, 2000

    2000

  3. [11]

    Upper bounds to the clique width of graphs

    Bruno Courcelle and Stephan Olariu. Upper bounds to the clique width of graphs. Discrete Appl. Math. , 101(1-3):77–114, 2000

    2000

  4. [12]

    Lawrence C. Eggan. Transition graphs and the star-heig ht of regular events. Michigan Math. J., 10:385–397, 1963

    1963

  5. [13]

    Fomin and Micha/suppress l Pilipczuk

    Fedor V. Fomin and Micha/suppress l Pilipczuk. Jungles, bundles, and fixed-parameter tractability. In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposiu m on Discrete Algorithms , pages 396–413. SIAM, Philadelphia, PA, 2013

    2013

  6. [14]

    Fomin and Micha/suppress l Pilipczuk

    Fedor V. Fomin and Micha/suppress l Pilipczuk. On width measuresand topological problems on semi- complete digraphs. J. Combin. Theory Ser. B , 138:78–165, 2019

    2019

  7. [15]

    Tournament pathwi dth and topological containment

    Alexandra Fradkin and Paul Seymour. Tournament pathwi dth and topological containment. J. Combin. Theory Ser. B , 103(3):374–384, 2013

    2013

  8. [16]

    Digraph width measures in parameterized algor ithmics

    Robert Ganian, Petr Hlinˇ en´ y, Joachim Kneis, Alexand er Langer, Jan Obdrˇ z´ alek, and Peter Rossmanith. Digraph width measures in parameterized algor ithmics. Discrete Appl. Math. , 168:88–107, 2014

    2014

  9. [17]

    Are there any good digraph width measures? J

    Robert Ganian, Petr Hlinˇ en´ y, Joachim Kneis, Daniel M eister, Jan Obdrˇ z´ alek, Peter Ross- manith, and Somnath Sikdar. Are there any good digraph width measures? J. Combin. Theory Ser. B , 116:250–286, 2016

    2016

  10. [18]

    Giannopoulou, Paul Hunter, and Dimitrios M

    Archontia C. Giannopoulou, Paul Hunter, and Dimitrios M. Thilikos. LIFO-search: A min–max theorem and a searching game for cycle-rank and tree -depth. Discrete Applied Math- ematics, 160(15):2089–2097, 2012

  11. [19]

    Digraph complexity measures and appli cations in formal language theory

    Hermann Gruber. Digraph complexity measures and appli cations in formal language theory. Discrete Math. Theor. Comput. Sci. , 14(2):189–204, 2012

    2012

  12. [20]

    Ac yclic coloring parameterized by directed clique-width

    Frank Gurski, Dominique Komander, and Carolin Rehs. Ac yclic coloring parameterized by directed clique-width. In Algorithms and discrete applied mathematics , volume 12601 of Lecture Notes in Comput. Sci. , pages 95–108. Springer, Cham, 2021

    2021

  13. [21]

    Directed width parameters on semicomplete digraphs

    Frank Gurski, Dominique Komander, Carolin Rehs, and Se bastian Wiederrecht. Directed width parameters on semicomplete digraphs. In Combinatorial optimization and applications , volume 13135 of Lecture Notes in Comput. Sci. , pages 615–628. Springer, Cham, [2021] ©2021

    2021

  14. [22]

    Unavoidable butterfly minors in digraphs of large cycle rank

    Meike Hatzel, O-joung Kwon, Myounghwan Lee, and Sebast ian Wiederrecht. Unavoidable butterfly minors in digraphs of large cycle rank. arXiv:2507.11814, 2025. 22

    2025

  15. [23]

    Digraph measures: Ke lly decompositions, games, and orderings

    Paul Hunter and Stephan Kreutzer. Digraph measures: Ke lly decompositions, games, and orderings. Theoretical Computer Science , 399(3):206–219, 2008

    2008

  16. [24]

    Ananth V. Iyer, H. Donald Ratliff, and Gopalakrishnan Vi jayan. Optimal node ranking of trees. Inform. Process. Lett. , 28(5):225–229, 1988

    1988

  17. [25]

    Seymour, and Robi n Thomas

    Thor Johnson, Neil Robertson, Paul D. Seymour, and Robi n Thomas. Directed tree-width. J. Combin. Theory Ser. B , 82(1):138–154, 2001

    2001

  18. [26]

    The rank-wid th of edge-coloured graphs

    Mamadou Moustapha Kant´ e and Michael Rao. The rank-wid th of edge-coloured graphs. The- ory Comput. Syst. , 52(4):599–644, 2013

    2013

  19. [27]

    Reducibility among combinatorial probl ems (1972)

    Richard Karp. Reducibility among combinatorial probl ems (1972). In Ideas that created the future—classic papers of computer science , pages 349–356. MIT Press, Cambridge, MA, [2021] ©2021. Reprinted from [0378476]

    1972

  20. [28]

    Digraphs of bounded width

    Stephan Kreutzer and O-joung Kwon. Digraphs of bounded width. In Jørgen Bang-Jensen and Gregory Gutin, editors, Classes of Directed Graphs , pages 405–466, Cham, 2018. Springer International Publishing

    2018

  21. [29]

    The loop complexity of regular even ts

    Robert McNaughton. The loop complexity of regular even ts. Information Sciences, 1(3):305– 328, 1969

    1969

  22. [30]

    Sub-exponential time parameterized algorithms for graph layout problems on digr aphs with bounded independence number

    Pranabendu Misra, Saket Saurabh, Roohani Sharma, and M eirav Zehavi. Sub-exponential time parameterized algorithms for graph layout problems on digr aphs with bounded independence number. Algorithmica, 85(7):2065–2086, 2023

  23. [31]

    Tree -depth, subgraph coloring and homo- morphism bounds

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Tree -depth, subgraph coloring and homo- morphism bounds. European J. Combin. , 27(6):1022–1041, 2006

    2006

  24. [32]

    Sparsity, volume 28 of Algorithms and Combinatorics

    Jaroslav Ne˘ set˘ ril and Patrice Ossona de Mendez. Sparsity, volume 28 of Algorithms and Combinatorics. Springer, Heidelberg, 2012. Graphs, structures, and algo rithms

    2012

  25. [33]

    DAG-width—connectivity measure for directed graphs

    Jan Obdrˇ z´ alek. DAG-width—connectivity measure for directed graphs. In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorit hms, pages 814–821. ACM, New York, 2006

    2006

  26. [34]

    Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings

    Micha/suppress l Pilipczuk. Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings. In 30th International Symposium on Theoretical Aspects of Com puter Science , volume 20 of LIPIcs. Leibniz Int. Proc. Inform. , pages 197–208. Schloss Dagstuhl. Leibniz...

    2013

  27. [35]

    Graph classes through the lens of logic

    Micha/suppress l Pilipczuk. Graph classes through the lens of logic. arXiv:2501.04166, 2025

    2025

  28. [36]

    A faster parameterized algorithm for treedepth

    Felix Reidl, Peter Rossmanith, Fernando S´ anchez Vill aamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming , pages 931–942, Ber- li...

    2014

  29. [37]

    Neil Robertson and Paul D. Seymour. Graph minors. II. Al gorithmic aspects of tree-width. J. Algorithms, 7(3):309–322, 1986. 23

    1986

  30. [38]

    Parameter ized algorithms for directed modular width

    Raphael Steiner and Sebastian Wiederrecht. Parameter ized algorithms for directed modular width. In Algorithms and discrete applied mathematics , volume 12016 of Lecture Notes in Comput. Sci. , pages 415–426. Springer, Cham, [2020] ©2020

    2020

  31. [39]

    Depth-first search and linear graph algo rithms

    Robert Tarjan. Depth-first search and linear graph algo rithms. SIAM J. Comput. , 1(2):146– 160, 1972. 24

    1972

Pith tools

Reviewed June 30, 2026 · model on record in the stance chip above.