Pith. sign in

REVIEW 1 major objections 42 references

Tournament Ranking: Duality and Efficiency

T0 review · 1 major / 0 minor · reviewed 2026-07-01 · grok-4.3

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

Pith's one-line read Cycle Mengerian tournaments admit combinatorial polynomial-time algorithms for minimum feedback arc sets and maximum cycle packings.

desk verdict 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. read the letter →

arxiv 2606.31565 v1 pith:RQL2A4XM submitted 2026-06-30 math.CO

Ge Song , Mengxi Yang , Wenan Zang This is my paper · ORCID
classification math.CO MSC 05C2005C85
keywords tournamentsfeedbackarcsetcyclepackingMengeriancombinatorialalgorithmspolynomialtimedirectedgraphs
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 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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

The 2020 structural characterization of CM tournaments can be converted into explicit, correct, and polynomial-time combinatorial procedures.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

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

1 major / 0 minor

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.

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 (1)
  1. [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).

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their review and for highlighting the need for explicit algorithmic content. We address the single major comment below.

read point-by-point responses

  1. Referee: [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).

    Authors: 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: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation builds on external 2020 characterization

full rationale

The paper's central contribution is the conversion of Chen et al. (2020)'s structural characterization of CM tournaments into explicit combinatorial polynomial-time algorithms for weighted min-FAS and max cycle packing. This characterization is cited as external prior work whose proof is non-algorithmic; the present paper supplies the algorithmic content. No self-citation load-bearing steps, no self-definitional reductions, no fitted inputs renamed as predictions, and no ansatz smuggling appear in the abstract or described derivation chain. The duality is stated as the definition of CM tournaments, and the algorithmic claim is presented as new. The work is self-contained against external benchmarks.

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

The paper introduces no new free parameters, invented entities, or ad-hoc axioms beyond standard graph-theoretic background.

assumptions (1)
  • standard math Standard definitions and properties of tournaments, feedback arc sets, and cycle packings from combinatorial optimization.
    The abstract invokes the known NP-hardness of feedback arc set and the 2020 characterization without re-deriving them.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tournament Ranking: Duality and Efficiency." pith.science (2026). https://pith.science/paper/RQL2A4XM

@misc{pith2026260631565,
  author       = {Pith},
  title        = {Pith review of: Tournament Ranking: Duality and Efficiency},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RQL2A4XM}},
  note         = {Machine review of arXiv:2606.31565}
}
abstract

The feedback arc set problem on tournaments arises in a rich variety of applications, and has been studied extensively in several research fields over the past six decades. It is well known that this problem is $NP$-hard and admits a polynomial-time approximation scheme (PTAS) in general. A tournament $T=(V, A)$ is called cycle Mengerian (CM) if, for every nonnegative integral weight function defined on $A$, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. In 2020 Chen et al. obtained a structural characterization of all CM tournaments; however, their proof is not algorithmic in nature. In this paper we present combinatorial polynomial-time algorithms for finding both minimum feedback arc sets and maximum cycle packings in arc-weighted CM tournaments.

Figures

Figures reproduced from arXiv: 2606.31565 by the authors.

Figure 1
Figure 1. Forbidden Structures Theorem 1.1. (Chen et al. [11, 12]) For a tournament T, the following statements are equiv￾alent: (i) T is M¨obius-free; (ii) T is cycle ideal; and (iii) T is cycle Mengerian. Their proof, however, is not algorithmic in nature. The purpose of this paper is to present combinatorial polynomial-time algorithms for solving both the FAS problem and the cycle pack￾ing problem on M¨obius-free tournamen… view at source ↗
Figure 2
Figure 2. F1 and G1 Theorem 2.1. (Chen et al. [13]) Let T = (V, A) be a strong tournament other than F1 and G1 (see [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Global Structure The proof of Theorem 2.1 yields a polynomial-time algorithm for exhibiting the desired global structure. Since the authors did not estimate the complexity of this algorithm, we provide one below. Recall from [11] that a dicut in a digraph G = (V, A) is a partition (X, Y ) of V such that all arcs between X and Y are directed from X to Y . A dicut (X, Y ) is called trivial if |X| = 1 or |Y | = 1. Furt… view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Network Construction The above definition of (Λ, Π)-flow is given in the arc-vertex form. An equivalent definition is formulated in the following path packing form: Let P be the set of all simple paths in N from Λ to Π. An (Λ, Π)-flow is an assignment g : P → R+ such t…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 42 canonical work pages

  1. [1]

    Ailon, M

    N. Ailon, M. Charikar, and A. Newman, Aggregating inconsistent information: ranking and clustering,J. ACM55(2008), no. 5, Art. 23, 27 pp

    work page 2008

  2. [2]

    I. Ali, W. Cook, and M. Kress, On the minimum violations ranking of a tournaments, Management Sci.32(1986), 660-672

    work page 1986

  3. [3]

    Alon, Ranking tournaments,SIAM J

    N. Alon, Ranking tournaments,SIAM J. Discrete Math.20(2006), 137-142

    work page 2006

  4. [4]

    Applegate, W

    D. Applegate, W. Cook, and S. McCormick, Integral infeasibility and testing total dual integrality,Oper. Res. Lett.10(1991), 37-41

    work page 1991

  5. [5]

    Barahona, J

    F. Barahona, J. Fonlupt, and A. Mahjoub, Compositions of graphs and polyhedra IV: Acyclic spanning subgraphs,SIAM J. Discrete Math.7(1994), 390-402

    work page 1994

  6. [6]

    Barahona and A

    F. Barahona and A. Mahjoub, Composition in the acyclic subdigraph polytope, Report No. 85371-OR, Institut f¨ ur¨Okonometrie und Operations Research, Universit¨ at Bonn, 1985

    work page 1985

  7. [7]

    Bessy, M

    S. Bessy, M. Bougeret, R. Krithika, A. Sahu, S. Saurabh, J. Thiebaut, and M. Zehavi, Packing arc-disjoint cycles in tournaments,Algorithmica83(2021), 1393–1420

    work page 2021

  8. [8]

    M. Cai, X. Deng, and W. Zang, An approximation algorithm for feedback vertex sets in tournaments,SIAM J. Comput.30(2001), 1993-2007

    work page 2001

Show all 42 references
  1. [9]

    Caprara, A

    A. Caprara, A. Panconesi, and R. Rizzi, Packing cycles in undirected graphs,J. Algorithms 48(2003), 239-256

    2003

  2. [10]

    X. Chen, G. Ding, X. Hu, and W. Zang, A min-max relation on packing feedback vertex sets,Math. Oper. Res.31(2006), 777-788

    2006

  3. [11]

    X. Chen, G. Ding, W. Zang, and Q. Zhao, Ranking tournaments with no errors I: Structural description,J. Combin. Theory Ser. B141(2020), 264-294. 25

    2020

  4. [12]

    X. Chen, G. Ding, W. Zang, and Q. Zhao, Ranking tournaments with no errors II: Minimax relation,J. Combin. Theory Ser. B142(2020), 244-275

    2020

  5. [13]

    X. Chen, G. Ding, W. Zang, and Q. Zhao, Packing feedback arc sets in tournaments exactly, Math. Oper. Res.49(2024), 151-170

    2024

  6. [14]

    Charbit, P

    P. Charbit, P. Thomass´ e, and A. Yeo, The minimum feedback arc set problem isN P-hard for tournaments,Combin. Probab. Comput.16(2007), 1-4

    2007

  7. [15]

    Coppersmith, L

    D. Coppersmith, L. Fleischer, and A. Rudra, Ordering by weighted number of wins gives a good ranking for weighted tournaments, in:Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms(SODA), 2006, pp. 776-782

    2006

  8. [16]

    Cormen, C

    T. Cormen, C. Leiserson, R. Rivest, and C. Stein,Introduction to Algorithms(4th Edition), The MIT Press, Cambridge, Massachusetts, 2022

    2022

  9. [17]

    G. Ding, L. Feng, and W. Zang, The complexity of recognizing linear systems with certain integrality properties,Math. Program. Ser. A114(2008), 321-334

    2008

  10. [18]

    G. Ding, Z. Xu, and W. Zang, Packing cycles in graphs, II,J. Combin. Theory Ser. B87 (2003), 244-253

    2003

  11. [19]

    Ding and W

    G. Ding and W. Zang, Packing cycles in graphs,J. Combin. Theory Ser. B86(2002), 381-407

    2002

  12. [20]

    Edmonds and R

    J. Edmonds and R. Giles, A min-max relation for submodular functions on graphs, in:Ann. Discrete Math.1, North-Holland, Amsterdam, 1977, pp. 185-204

    1977

  13. [21]

    Erd˝ os and J

    P. Erd˝ os and J. Moon, On sets of consistent arcs in tournaments,Canad. Math. Bull.8 (1965), 269-271

    1965

  14. [22]

    G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs,Algorithmica20(1998), 151-174

    1998

  15. [23]

    G. Even, J. Naor, and L. Zosin, An 8-approximation algorithm for the subset feedback vertex set problem,SIAM J. Comput.30(2000), 1231-1252

    2000

  16. [24]

    Fulkerson, Upsets in round robin tournaments,Canad

    D. Fulkerson, Upsets in round robin tournaments,Canad. J. Math.17(1965), 957-969

    1965

  17. [25]

    Geelen and B

    J. Geelen and B. Guenin, Packing odd circuits in Eulerian graphs,J. Combin. Theory Ser. B86(2002), 280-295

    2002

  18. [26]

    Gr¨ otschel, L

    M. Gr¨ otschel, L. Lov´ asz, and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,Combinatorica1(1981), 169-197

    1981

  19. [27]

    Guenin, Circuit Mengerian directed graphs, in:Integer Programming and Combinatorial Optimization(Utrecht, 2001), Lecture Notes in Comput

    B. Guenin, Circuit Mengerian directed graphs, in:Integer Programming and Combinatorial Optimization(Utrecht, 2001), Lecture Notes in Comput. Sci. 2081, pp. 185-195

    2001

  20. [28]

    Guenin, A short proof of Seymour’s characterization of the matroids with the max-flow min-cut property,J

    B. Guenin, A short proof of Seymour’s characterization of the matroids with the max-flow min-cut property,J. Combin. Theory Ser. B86(2002), 273-279

    2002

  21. [29]

    Guenin and R

    B. Guenin and R. Thomas, Packing directed circuits exactly,Combinatorica31(2011), 397-421

    2011

  22. [30]

    J¨ unger,Polyhedral Combinatorics and the Acyclic Subdigraph Problem, Heldermann Verlag, Berlin, 1985

    M. J¨ unger,Polyhedral Combinatorics and the Acyclic Subdigraph Problem, Heldermann Verlag, Berlin, 1985. 26

    1985

  23. [31]

    Krivelevich, Z

    M. Krivelevich, Z. Nutov, M. Salavatipour, J. Verstraete, and R. Yuster, Approximation algorithms and hardness results for cycle packing problems,ACM Trans. Algorithms, Vol. 3, No. 4, Article 48, 2007

    2007

  24. [32]

    Lucchesi and D

    C. Lucchesi and D. Younger, A minimax theorem for directed graphs,J. London Math. Soc.17(1978), 369-374

    1978

  25. [33]

    Mathieu and W

    C. Mathieu and W. Schudy, How to rank with few errors: A PTAS for weighted feedback arc set on tournaments, in:Proc. 39th Annual ACM Symposium on Theory of Comput. (STOC’07), pp. 95-103, ACM, New York, 2007

    2007

  26. [34]

    Seymour, The matroids with the max-flow min-cut property,J

    P. Seymour, The matroids with the max-flow min-cut property,J. Combin. Theory Ser. B 23(1977), 189-222

    1977

  27. [35]

    Seymour, Packing directed circuits fractionally,Combinatorica15(1995), 281–288

    P. Seymour, Packing directed circuits fractionally,Combinatorica15(1995), 281–288

    1995

  28. [36]

    Seymour, Packing circuits in eulerian digraphs,Combinatorica16(1996), 223-231

    P. Seymour, Packing circuits in eulerian digraphs,Combinatorica16(1996), 223-231

    1996

  29. [37]

    Slater, Inconsistencies in a schedule of paired comparisons,Biometrika48(1961), 303- 312

    P. Slater, Inconsistencies in a schedule of paired comparisons,Biometrika48(1961), 303- 312

    1961

  30. [38]

    Spencer, Optimal ranking of tournaments,Networks1(1971), 135-138

    J. Spencer, Optimal ranking of tournaments,Networks1(1971), 135-138

    1971

  31. [39]

    Tarjan, Depth-first search and linear graph algorithms,SIAM J

    R. Tarjan, Depth-first search and linear graph algorithms,SIAM J. Comput.1(1972), 146-160

    1972

  32. [40]

    Tarjan, A simple version of Karzanov’s blocking flow algorithm,Oper

    R. Tarjan, A simple version of Karzanov’s blocking flow algorithm,Oper. Res. Lett.2 (1984), 265-268

    1984

  33. [41]

    van Zuylen and D

    A. van Zuylen and D. Williamson, Deterministic pivoting algorithms for constrained ranking and clustering problems,Math. Oper. Res.34(2009), 594-620

    2009

  34. [42]

    Younger, Minimum feedback arc sets for a directed graphs,IEEE Trans

    D. Younger, Minimum feedback arc sets for a directed graphs,IEEE Trans. Circuit Theory 10(1963), 238-245. 27

    1963

Pith tools

Reviewed July 1, 2026 · model on record in the stance chip above.