{"id":"186a3038-62a8-4b62-86fb-6d136d40a79a","arxiv_id":"2606.31565","paper_version":1,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper supplies combinatorial poly-time algorithms for min feedback arc set and max cycle packing in arc-weighted cycle Mengerian tournaments.","lead":"This paper gives combinatorial polynomial-time algorithms to compute minimum weighted feedback arc sets and maximum cycle packings in cycle Mengerian tournaments. A smart generalist might read it for efficient exact methods on a subclass of an NP-hard ranking problem that arises in competitions and decision systems.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"No significant objection identified","rationale":"The reader's weakest assumption matches the load-bearing step exactly. With only the abstract available in the query, no further technical flaw can be isolated. If the full manuscript supplies the explicit procedures, the claim stands; the current information does not reveal a place where the required condition fails.","tokens_in":1611,"tokens_out":249,"duration_ms":29268,"concrete_test":"Extract the algorithm descriptions (likely in Sections 3-5) and verify that each step is combinatorial (no LP solvers or oracles) and runs in time polynomial in |V| and the bit length of the weights; confirm the claimed running time bound holds.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim is that the 2020 structural characterization of CM tournaments yields explicit combinatorial polynomial-time algorithms for weighted min-FAS and max cycle packing. The provided abstract states that such algorithms are presented. No internal inconsistency, hidden non-combinatorial step, or unsupported conversion is visible in the given material. The duality holds by definition of CM tournaments, and the claim that the characterization can be made algorithmic is consistent with the paper's stated contribution.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims to present combinatorial polynomial-time algorithms for computing minimum feedback arc sets and maximum cycle packings in arc-weighted cycle Mengerian (CM) tournaments. It builds directly on the 2020 structural characterization of CM tournaments due to Chen et al., converting that non-algorithmic result into explicit procedures that exploit the min-FAS = max cycle packing duality.","tokens_in":1678,"tokens_out":269,"duration_ms":24861,"significance":"If the claimed algorithms are correct, combinatorial, and polynomial-time, the work would be significant: it supplies efficient, non-LP methods for an important subclass of tournaments in which the feedback arc set problem is known to be tractable via duality, while the general problem remains NP-hard. The explicit algorithmic conversion of a structural theorem is a clear strength.","major_comments":[{"comment":"The abstract asserts that explicit combinatorial polynomial-time algorithms are presented, yet the provided manuscript text contains no algorithm descriptions, pseudocode, complexity analyses, or proofs of correctness. Without these sections it is impossible to verify that the 2020 characterization has been turned into correct, polynomial procedures (see reader's soundness assessment).","section":"Abstract / main body"}],"minor_comments":[],"recommendation":"uncertain","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their review and for highlighting the need for explicit algorithmic content. We address the single major comment below.","responses":[{"response":"The referee is correct: the submitted manuscript contains only the high-level claim in the abstract and does not include the promised algorithm descriptions, pseudocode, complexity analysis, or correctness proofs. This is an omission in the current draft. We will revise the manuscript by adding a dedicated algorithmic section that converts the Chen et al. structural characterization into explicit combinatorial procedures, including pseudocode for both min-FAS and max cycle packing, a polynomial-time bound, and proofs of correctness that rely on the established duality.","revision_made":"yes","referee_comment":"[Abstract / main body] The abstract asserts that explicit combinatorial polynomial-time algorithms are presented, yet the provided manuscript text contains no algorithm descriptions, pseudocode, complexity analyses, or proofs of correctness. Without these sections it is impossible to verify that the 2020 characterization has been turned into correct, polynomial procedures (see reader's soundness assessment)."}],"tokens_in":1171,"tokens_out":237,"duration_ms":22769,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The main takeaway is that Song, Yang, and Zang have produced combinatorial polynomial-time algorithms for minimum weighted feedback arc sets and maximum cycle packings in arc-weighted CM tournaments. This is the direct algorithmic follow-up to the 2020 Chen et al result, which established the duality but stayed non-algorithmic.\n\nThe paper does a clean job of stating the setting and the gap it fills. It notes the general NP-hardness and the PTAS for arbitrary tournaments, then focuses on the CM subclass where the min-FAS weight equals the max packing size for any nonnegative integral weights. Delivering combinatorial procedures rather than LP-based methods keeps the work explicit and potentially more insightful for the structure.\n\nThe soft spots are limited. The abstract gives no sketch of the algorithms or running-time arguments, so the full paper must show that the conversion from the structural characterization is straightforward, polynomial, and stays combinatorial without hidden steps or oracles. The assumption that the 2020 result yields such procedures looks reasonable on the surface, and the stress-test found no internal inconsistency, but the details need checking.\n\nThis is for researchers working on feedback arc set in tournaments, Mengerian properties, or exact algorithms for restricted classes of NP-hard problems. Someone interested in how structural characterizations translate to computation would find it useful.\n\nIt deserves peer review to verify the algorithm descriptions and proofs. I recommend sending it out rather than desk-rejecting.","headline":"The paper turns Chen et al's 2020 structural characterization of CM tournaments into explicit combinatorial polynomial-time algorithms for weighted min-FAS and max cycle packing.","tokens_in":2123,"tokens_out":367,"would_cite":false,"duration_ms":32489,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C20","05C85"],"pacs":[],"model":"grok-4.3","headline":"Cycle Mengerian tournaments admit combinatorial polynomial-time algorithms for minimum feedback arc sets and maximum cycle packings.","keywords":["tournaments","feedback arc set","cycle packing","cycle Mengerian","combinatorial algorithms","polynomial time","directed graphs"],"falsifier":"A single arc-weighted CM tournament on which either the computed feedback arc set weight exceeds the maximum cycle packing size or the running time exceeds any fixed polynomial bound.","tokens_in":2512,"feed_emoji":"","tokens_out":609,"duration_ms":22825,"temperature":0.7,"pith_summary":"The paper converts a 2020 structural characterization of cycle Mengerian tournaments into explicit algorithms that compute both the minimum-weight feedback arc set and the maximum cycle packing for any nonnegative integral arc weights. A tournament is cycle Mengerian when these two quantities are always equal. The algorithms are combinatorial, meaning they rely on direct graph operations rather than general-purpose solvers, and they run in polynomial time. This supplies an efficient exact method for a subclass of tournaments where the general feedback arc set problem remains NP-hard.","feed_headline":"Poly-time algorithms find exact feedback arc sets in CM tournaments","feed_subtitle":"Cycle Mengerian tournaments now have combinatorial procedures for minimum arc deletions and maximum cycle packings under any integral weight","key_machinery":"The structural characterization of cycle Mengerian tournaments, which is used to guide the construction of the feedback arc set and the cycle packing via direct combinatorial reductions.","core_discovery":"Chen et al.'s structural characterization of CM tournaments can be turned into combinatorial polynomial-time procedures that, for any arc-weighted CM tournament, return a minimum-weight feedback arc set together with a maximum cycle packing whose total weight equals the packing size.","pith_inferences":["The same structural description may support fast algorithms for related problems such as minimum vertex feedback sets inside CM tournaments.","If many real-world ranking instances turn out to be CM, the algorithms would yield practical exact solutions without approximation.","The approach could be tested by generating random tournaments and checking whether the output sets satisfy the weight-equality condition on known CM examples."],"forward_implications":["Exact minimum feedback arc sets become computable in polynomial time for every arc-weighted CM tournament.","Maximum cycle packings can be found in the same time bound and certify optimality via the duality equality.","Any ranking or ordering problem that reduces to feedback arc set on a CM tournament instance now has an efficient exact solver.","The Mengerian equality holds constructively rather than only existentially for this tournament class."],"fun_headline_variants":["Poly-time combinatorial exact feedback arcs for CM tournaments","Min feedback sets computed polynomially in cycle Mengerian tournaments","Combinatorial algorithms for max cycle packings in weighted CM tournaments","Poly-time procedures for feedback arcs and cycle packings in CM tournaments"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The 2020 structural characterization of CM tournaments can be converted into explicit, correct, and polynomial-time combinatorial procedures.","fun_headline_variants_meta":{"raw":{"variants":["Poly-time combinatorial exact feedback arcs for CM tournaments","Min feedback sets computed polynomially in cycle Mengerian tournaments","Combinatorial algorithms for max cycle packings in weighted CM tournaments","Poly-time procedures for feedback arcs and cycle packings in CM tournaments"]},"model":"grok-4.3","cost_usd":0.003471,"raw_usage":{"total_tokens":1772,"prompt_tokens":552,"num_sources_used":0,"completion_tokens":68,"cost_in_usd_ticks":34712000,"prompt_tokens_details":{"text_tokens":552,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1152,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":552,"tokens_out":68,"duration_ms":10607,"temperature":1.0,"reasoning_tokens":1152,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-01T04:51:59.773616+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"A single arc-weighted CM tournament on which either the computed feedback arc set weight exceeds the maximum cycle packing size or the running time exceeds any fixed polynomial bound.","supporting_citations":[],"review_version":1}