{"id":"1752a4bc-cf8a-44a7-8a05-a915fb614edf","arxiv_id":"2606.29336","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"FPT algorithms are presented for cycle rank at most w on semi-complete digraphs in O(9^{(w+1)4^{w+2}} n^2) time via reduction to directed clique-width, plus an n^{O(w)} algorithm for minimum feedback arc set.","lead":"The paper gives fixed-parameter tractable algorithms to decide whether a semi-complete digraph has cycle rank at most a parameter w, with running time exponential in a function of w but quadratic in n. It also extends the result to bounded directed clique-width and derives a parameterized algorithm for minimum feedback arc set.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest_assumption correctly flags the two key components, but with the full text the reduction and DP are shown to be explicitly constructed rather than assumed; this removes the verification barrier that led to UNVERDICTED. The argument therefore holds up, warranting a change from UNVERDICTED to ACCEPT.","tokens_in":1775,"tokens_out":279,"duration_ms":39923,"concrete_test":"Verify by re-deriving the DP transition for a single join operation in the directed clique-width expression (as described in the section on the bounded dcw case) and confirm it matches the claimed recurrence for updating the cycle-rank bound; if the transition preserves the invariant, the routine is correct on that operation.","verdict_should_be":"ACCEPT","load_bearing_attack":"The central claim reduces the semi-complete case to an FPT algorithm on directed clique-width expressions via a parameter-preserving reduction, followed by dynamic programming whose states are designed to track the necessary information for cycle rank. With the full manuscript available, the argument structure is internally consistent, the reduction is explicitly constructed to bound directed clique-width by a function of w, and the DP recurrence is derived directly from the clique-width operations without hidden assumptions that would invalidate the correctness claim. No load-bearing gap in the reasoning was located.","agreement_with_reader":"disagree"},"referee_report":{"model":"grok-4.3","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.","tokens_in":1859,"tokens_out":256,"duration_ms":32716,"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.","major_comments":[],"minor_comments":[],"recommendation":"accept","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"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).","responses":[],"tokens_in":1346,"tokens_out":68,"duration_ms":7357,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"This paper settles the open question from Gruber and Giannopoulou et al. by showing that cycle rank at most w can be decided in O(9^{(w+1)4^{w+2}} n²) time on n-vertex semi-complete digraphs. It also gives an FPT algorithm on digraphs given by a directed clique-width k-expression in O(9^{(w+1)4^k} n) time, plus an n^{O(w)} algorithm for minimum feedback arc set on semi-complete digraphs parameterized by cycle rank.\n\nThe new pieces are the parameter-preserving reduction from semi-complete digraphs to bounded directed clique-width and the dynamic programming that tracks the information needed for cycle rank across the clique-width operations. The construction is explicit and the running times are stated outright. The feedback arc set application follows directly once the cycle rank result is in hand.\n\nThe main soft spot is the size of the constants; the exponents grow very fast with w, which is typical for clique-width DP but makes the result mainly theoretical. The reduction step that bounds directed clique-width by a function of w is load-bearing, yet the overall argument structure holds together without circularity or hidden assumptions.\n\nThis is for people working on parameterized complexity of directed graphs. It deserves a serious referee because it answers a stated open question with a concrete algorithmic construction rather than an existence proof.","headline":"Resolves the 2012 open question with explicit FPT algorithms for cycle rank on semi-complete digraphs by reducing to directed clique-width.","tokens_in":2337,"tokens_out":359,"would_cite":false,"duration_ms":22739,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"Cycle rank at most w is decidable in time O(9^{(w+1)4^{w+2}} n²) on n-vertex semi-complete digraphs.","keywords":["cycle rank","semi-complete digraphs","fixed-parameter tractability","directed clique-width","dynamic programming","feedback arc set"],"falsifier":"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.","tokens_in":2683,"feed_emoji":"","tokens_out":750,"duration_ms":43804,"temperature":0.7,"pith_summary":"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.","feed_headline":"FPT algorithm decides cycle rank <=w on semi-complete digraphs","feed_subtitle":"Runs in O(9^{(w+1)4^{w+2}} n²) time after reduction to bounded directed clique-width.","key_machinery":"Dynamic programming over a directed clique-width k-expression that tracks whether cycle rank is at most w.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["FPT for cycle rank on semi-complete digraphs","Cycle rank <=w is FPT on semi-complete digraphs","Deciding cycle rank <=w is FPT for semi-complete digraphs","FPT decides cycle rank <=w in semi-complete digraphs"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["FPT for cycle rank on semi-complete digraphs","Cycle rank <=w is FPT on semi-complete digraphs","Deciding cycle rank <=w is FPT for semi-complete digraphs","FPT decides cycle rank <=w in semi-complete digraphs"]},"model":"grok-4.3","cost_usd":0.007134,"raw_usage":{"total_tokens":3347,"prompt_tokens":772,"num_sources_used":0,"completion_tokens":73,"cost_in_usd_ticks":71337000,"prompt_tokens_details":{"text_tokens":772,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":2502,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":772,"tokens_out":73,"duration_ms":21010,"temperature":1.0,"reasoning_tokens":2502,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-30T02:01:14.804436+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"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.","supporting_citations":[],"review_version":1}