pith. machine review for the scientific record. sign in

arxiv: 2605.10599 · v1 · submitted 2026-05-11 · 🧮 math.OC

Recognition: no theorem link

Novel neighborhood structures for incomplete round robin sports tournaments

Karel Devriesere , David Van Bulck , Dries Goossens
Authors on Pith no claims yet

Pith reviewed 2026-05-12 04:30 UTC · model grok-4.3

classification 🧮 math.OC
keywords incomplete round-robinsports schedulingneighborhood searchlocal searchhill climbinggraph theorytournament timetabling
0
0 comments X

The pith

Two new neighborhood structures connect the solution space for incomplete round-robin tournament schedules and improve local search performance.

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

The paper develops two new ways to modify schedules in incomplete round-robin tournaments, where each team plays the same number of games against only some of the others. One neighborhood adds a single new game and then makes a short chain of adjustments to restore feasibility. The other changes multiple games but confines all alterations to one round, and this structure is shown to link every possible feasible schedule to every other. These neighborhoods are placed inside an adaptive late acceptance hill climbing method, which then finds high-quality schedules and improves on the best known solutions for several published test sets. If effective, this approach could help sports organizers create fairer and more balanced timetables with less manual effort.

Core claim

The authors introduce two neighborhood structures described in graph theory terms for the incomplete round-robin sports tournament scheduling problem. The first structure introduces a single new game followed by a minimal repair chain. The second introduces possibly many new games but only affects a single round. The latter neighborhood is proven to fully connect the solution space. When embedded in an adaptive late acceptance hill climbing algorithm, the neighborhoods lead to high quality solutions and new best known solutions on literature instances.

What carries the argument

The single-round neighborhood structure that fully connects the feasible solution space by allowing changes to multiple games within one round only.

If this is right

  • Any two feasible schedules can be transformed into each other through a sequence of single-round neighborhood moves.
  • Local search algorithms using these neighborhoods can explore the entire solution space without getting stuck in disconnected components.
  • The adaptive hill climbing algorithm achieves new best solutions for multiple benchmark instances from the literature.
  • The proposed methods apply directly to scheduling youth and professional sports events using the incomplete round-robin format.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The connectivity result might allow development of exact optimization methods that use these moves to enumerate or search the full space.
  • Organizers could integrate these structures into commercial scheduling software to generate improved timetables automatically.
  • Similar neighborhood ideas may apply to related problems like complete round-robins or other combinatorial scheduling tasks with round constraints.

Load-bearing premise

That the mathematical graph model of the tournament accurately represents all practical constraints and that the existing benchmark instances reflect real-world scheduling needs sufficiently well.

What would settle it

Finding two feasible schedules that cannot be connected by any sequence of single-round moves, or showing that the algorithm does not improve solution quality on a new set of realistic tournament instances.

Figures

Figures reproduced from arXiv: 2605.10599 by David Van Bulck, Dries Goossens, Karel Devriesere.

Figure 1
Figure 1. Figure 1: Equivalence between a set of disjoint perfect matchings and an iRR timetable. Dashed edges [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of RS and PRS with rounds R2 (purple) and R3 (blue) [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 4
Figure 4. Figure 4: CR of (1,2,3,4,6,1) 3 2 1 8 7 6 5 4 (a) Initial orientation 3 2 1 8 7 6 5 4 (b) Orientation after CR 3.4 Cycle and Path Reversal (CR and PR) The move cycle reversal (CR), first proposed by Knust and von Thaden (2006) for RR tournaments, takes as input a balanced cycle and reverses its edges. For an illustration of this neighborhood, see [PITH_FULL_IMAGE:figures/full_fig_p007_4.png] view at source ↗
Figure 8
Figure 8. Figure 8: Graph with no balanced alternating cycle [PITH_FULL_IMAGE:figures/full_fig_p012_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: iPRS-U 3 2 1 8 7 6 5 4 +1H +1A (a) Coloring after iPRS-U 3 2 1 8 7 6 5 4 +1H +1A (b) Path (2,7,6,8,1) from 2 to 1 3 2 1 8 7 6 5 4 +0H +0A (c) Orientation after path reversal 4 Connectivity results In this section, we present our theoretical results concerning the connectivity of the neighborhoods. 4.1 Cycle and Path Reversal In Knust and von Thaden (2006), it is shown that CR is orientation-wise connected … view at source ↗
Figure 10
Figure 10. Figure 10: Illustration of iPTS (iPRS) escaping from perfect one-factorization [PITH_FULL_IMAGE:figures/full_fig_p014_10.png] view at source ↗
Figure 13
Figure 13. Figure 13: Gaps football instances instances may have several reasons. First, in contrast to iTTP instances, YSTP instances impose many constraints on the home-away patterns of teams. In our framework, we only accept candidate solutions if they are feasible, suggesting that neighborhood structures with a minimum impact on the home-away patterns may fare well for YSTP instances. By complementing iPTS with CR within t… view at source ↗
read the original abstract

The incomplete round robin sports tournament format, where each team plays the same number of games but faces only a subset of the other teams, is becoming increasingly popular in both youth and professional competitions. In contrast to conventional round robin tournaments, however, neighborhood structures for scheduling incomplete round robin tournaments have largely remained unexplored. We fill this gap by proposing two novel neighborhood structures and describe them in graph theory terms. One of them introduces a single new game followed by a minimal repair chain, while the other introduces possibly many new games but only affects a single round. The latter is shown to fully connect the solution space. We embed the neighborhoods in an adaptive late acceptance hill climbing algorithm and show that the proposed algorithm obtains high quality and new best solutions for several sets of instances from the literature, thereby empirically confirming the effectiveness of the proposed neighborhoods.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper proposes two novel neighborhood structures for local search in scheduling incomplete round-robin tournaments, modeled via graph theory. The first adds one new game followed by a minimal repair chain; the second adds multiple games but affects only a single round and is shown to fully connect the feasible solution space. These neighborhoods are embedded in an adaptive late acceptance hill-climbing algorithm that produces high-quality schedules and new best solutions on several literature benchmark instances.

Significance. If the connectivity proof holds under the stated model, the work provides a theoretically grounded advance in neighborhood design for sports scheduling, ensuring local search can reach any feasible solution and thereby improving reliability over potentially disconnected neighborhoods. The empirical demonstration of new best solutions on external literature instances is a concrete strength, as is the explicit graph-theoretic formulation that makes the neighborhoods precise and analyzable.

major comments (2)
  1. [§3.2] §3.2 (connectivity of the second neighborhood): The claim that this neighborhood fully connects the solution space is load-bearing for the theoretical contribution. The proof sketch must explicitly verify that sequences of single-round multi-game moves always preserve the global constraint that each team plays exactly k games in total, without creating temporary violations that cannot be repaired within the neighborhood definition.
  2. [§5] §5 (computational experiments): The assertion of obtaining new best solutions on literature instances is central to the empirical validation. The manuscript should report, for each improved instance, the previous best objective value (with citation), the new value, the number of independent runs, and any statistical comparison to confirm the improvement is not due to post-hoc parameter tuning of the late-acceptance mechanism.
minor comments (2)
  1. [Abstract / §1] The abstract and §1 should briefly indicate the precise definition of an incomplete round-robin (each team plays exactly k opponents) to orient readers unfamiliar with the format.
  2. [§3] Notation in §3 for the underlying graph G and the round structure could be introduced with a small illustrative example to improve readability of the neighborhood definitions.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive evaluation and the precise comments that help clarify and strengthen the presentation. We respond to each major comment below and indicate the revisions that will be incorporated.

read point-by-point responses

  1. Referee: [§3.2] §3.2 (connectivity of the second neighborhood): The claim that this neighborhood fully connects the solution space is load-bearing for the theoretical contribution. The proof sketch must explicitly verify that sequences of single-round multi-game moves always preserve the global constraint that each team plays exactly k games in total, without creating temporary violations that cannot be repaired within the neighborhood definition.

    Authors: We appreciate the referee drawing attention to the need for explicit verification in the connectivity argument. The second neighborhood is constructed so that every move replaces a collection of games within one round while preserving both the per-round matching constraints and the total degree k of every team in the underlying graph; because the change is degree-neutral with respect to the global schedule, each individual move maps a feasible solution to another feasible solution. Consequently, no temporary violations of the global constraint arise, and every intermediate solution remains repairable by definition of the neighborhood. In the revised manuscript we will insert a short preliminary lemma in §3.2 that formally states this degree-preservation property before proceeding to the connectivity theorem, thereby making the proof sketch fully self-contained. revision: yes

  2. Referee: [§5] §5 (computational experiments): The assertion of obtaining new best solutions on literature instances is central to the empirical validation. The manuscript should report, for each improved instance, the previous best objective value (with citation), the new value, the number of independent runs, and any statistical comparison to confirm the improvement is not due to post-hoc parameter tuning of the late-acceptance mechanism.

    Authors: We agree that expanded reporting will increase the transparency and reproducibility of the empirical results. In the revised §5 we will add a summary table that, for every instance on which a new best solution was obtained, lists the previous best objective value together with its literature citation, the new objective value achieved, the number of independent runs performed, and the outcome of a statistical test (Wilcoxon signed-rank) comparing the distribution of our results against the previous best. The adaptive late-acceptance parameters were fixed after preliminary tuning on a separate collection of instances, as already described in the manuscript; the additional statistical information will further confirm that the reported improvements are not attributable to post-hoc tuning on the test set. revision: yes

Circularity Check

0 steps flagged

No circularity; neighborhoods and connectivity proof are independently defined

full rationale

The paper defines two new neighborhood structures directly in graph-theoretic terms (one via single-game insertion plus repair chain, the other via multi-game single-round changes) and states that the second 'is shown to fully connect the solution space.' This connectivity claim is presented as a proof result rather than a self-referential fit or renaming. The algorithm is then tested on external literature instances for empirical performance. No self-citations are load-bearing in the provided text, no parameters are fitted and relabeled as predictions, and no ansatz or uniqueness theorem is smuggled in via prior author work. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard graph-theory modeling of matches and rounds plus conventional local-search concepts; no free parameters, ad-hoc axioms, or new invented entities are introduced beyond the two neighborhood definitions themselves.

axioms (1)
  • standard math Schedules can be represented as graphs where edges correspond to games and rounds are partitions with degree constraints
    The neighborhoods are defined and analyzed in graph-theory terms as stated in the abstract.

pith-pipeline@v0.9.0 · 5437 in / 1357 out tokens · 48166 ms · 2026-05-12T04:30:24.537359+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

66 extracted references · 66 canonical work pages

  1. [1]

    2025 , author =

    Beyond leagues: A single incomplete round robin tournament for multi-league sports timetabling , journal =. 2025 , author =

    work page 2025

  2. [2]

    Statistical Modelling , volume=

    The efficacy of league formats in ranking teams , author=. Statistical Modelling , volume=. 2018 , publisher=

    work page 2018

  3. [3]

    Van Bulck, David and Goossens, Dries and Sch. Robin. European Journal of Operational Research , volume=. 2020 , publisher=

    work page 2020

  4. [4]

    Fair incomplete tournaments , author=. Bull. of ICA , volume=

    work page

  5. [5]

    Congressus numerantium , volume=

    Fair incomplete tournaments with odd number of teams and large number of games , author=. Congressus numerantium , volume=. 2007 , publisher=

    work page 2007

  6. [6]

    , title =

    Froncek, D. , title =. AKCE International Journal of Graphs and Combinatorics , year =

    work page

  7. [7]

    and Shepanik, A

    Froncek, D. and Shepanik, A. , title =. Journal of Algebra Combinatorics Discrete Structures and Applications , year =

    work page

  8. [8]

    Redesigning

    Devriesere, Karel and Goossens, Dries , journal=. Redesigning. 2025 , publisher=

    work page 2025

  9. [9]

    2023 , publisher=

    Combinatorial models for scheduling sports tournaments , author=. 2023 , publisher=

    work page 2023

  10. [10]

    Multi-neighborhood simulated annealing for the sports timetabling competition

    Rosati, Roberto Maria and Petris, Matteo and Di Gaspero, Luca and Schaerf, Andrea , journal=. Multi-neighborhood simulated annealing for the sports timetabling competition. 2022 , publisher=

    work page 2022

  11. [11]

    Journal of Scheduling , volume=

    A simulated annealing approach to the traveling tournament problem , author=. Journal of Scheduling , volume=. 2006 , publisher=

    work page 2006

  12. [12]

    European Journal of Operational Research , volume=

    Heuristics for the mirrored traveling tournament problem , author=. European Journal of Operational Research , volume=. 2007 , publisher=

    work page 2007

  13. [13]

    Journal of Scheduling , volume=

    A heuristic for minimizing weighted carry-over effects in round robin tournaments , author=. Journal of Scheduling , volume=. 2011 , publisher=

    work page 2011

  14. [14]

    Costa, Fabr. An. Annals of Operations Research , volume=. 2012 , publisher=

    work page 2012

  15. [15]

    Journal of Heuristics , volume=

    A composite-neighborhood tabu search approach to the traveling tournament problem , author=. Journal of Heuristics , volume=. 2007 , publisher=

    work page 2007

  16. [16]

    Discrete Optimization , volume=

    Balanced home--away assignments , author=. Discrete Optimization , volume=. 2006 , publisher=

    work page 2006

  17. [17]

    Annals of Operations Research , volume=

    The sport teams grouping problem , author=. Annals of Operations Research , volume=. 2019 , publisher=

    work page 2019

  18. [18]

    On perfect one-factorization of the complete graph

    Kobayashi, Midori , journal=. On perfect one-factorization of the complete graph. 1989 , publisher=

    work page 1989

  19. [19]

    Discrete Applied Mathematics , volume=

    Sports scheduling search space connectivity: A riffle shuffle driven approach , author=. Discrete Applied Mathematics , volume=. 2016 , publisher=

    work page 2016

  20. [20]

    Studies on graphs and discrete programming , volume=

    Scheduling in sports , author=. Studies on graphs and discrete programming , volume=. 1981 , publisher=

    work page 1981

  21. [21]

    Proceedings of the London Mathematical Society , volume=

    Some theorems on abstract graphs , author=. Proceedings of the London Mathematical Society , volume=. 1952 , publisher=

    work page 1952

  22. [22]

    A greedy algorithm for the social golfer and the

    Schmand, Daniel and Schr. A greedy algorithm for the social golfer and the. European Journal of Operational Research , volume=. 2022 , publisher=

    work page 2022

  23. [23]

    Algorithmica , volume=

    Diverse pairs of matchings , author=. Algorithmica , volume=. 2024 , publisher=

    work page 2024

  24. [24]

    On the initial transition of graphs of

    Kashiwagi, Yusuke and Yamamoto, Masaki and Yashima, Takamasa , journal=. On the initial transition of graphs of. 2025 , publisher=

    work page 2025

  25. [25]

    2026 , journal=

    The incomplete Traveling Tournament Problem , author=. 2026 , journal=

    work page 2026

  26. [26]

    Recoloring subgraphs of

    Urrutia, Sebasti. Recoloring subgraphs of. Theoretical Computer Science , volume=. 2021 , publisher=

    work page 2021

  27. [27]

    Mathematical Programming Computation , volume=

    Blossom V: a new implementation of a minimum cost perfect matching algorithm , author=. Mathematical Programming Computation , volume=. 2009 , publisher=

    work page 2009

  28. [28]

    1976 , publisher=

    Graph theory with applications , author=. 1976 , publisher=

    work page 1976

  29. [29]

    Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    The complexity of satisfiability problems , author=. Proceedings of the tenth annual ACM symposium on Theory of computing , pages=

    work page

  30. [30]

    Omega , Year =

    Sports league scheduling: Graph- and resource-based models , Author =. Omega , Year =

    work page

  31. [31]

    and Urrutia, S

    Januario, T. and Urrutia, S. and Celso, C. R. and de Werra, D. , title =. European Journal of Operational Research , year =

    work page

  32. [32]

    and Urrutia, S

    Januario, T. and Urrutia, S. , title =. Operations research and computing: algorithms and software for analytics, 1st ed. Richmond, VI: INFORMS , year =

    work page

  33. [33]

    Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=

    Edge-coloring algorithms for bounded degree multigraphs , author=. Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) , pages=. 2024 , organization=

    work page 2024

  34. [34]

    2009 , publisher=

    Digraphs: theory, algorithms and applications , author=. 2009 , publisher=

    work page 2009

  35. [35]

    Discrete mathematics , volume=

    A characterization of the minimum cycle mean in a digraph , author=. Discrete mathematics , volume=. 1978 , publisher=

    work page 1978

  36. [36]

    Numerische Mathematik , bolume=

    A note on two problems in connexion with graphs , author=. Numerische Mathematik , bolume=

    work page

  37. [37]

    Hopcroft, John E and Karp, Richard M , journal=. An n\^. 1973 , publisher=

    work page 1973

  38. [38]

    Journal of the ACM (JACM) , volume=

    A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries , author=. Journal of the ACM (JACM) , volume=. 2004 , publisher=

    work page 2004

  39. [39]

    Journal of the society for industrial and applied mathematics , volume=

    Algorithms for the assignment and transportation problems , author=. Journal of the society for industrial and applied mathematics , volume=. 1957 , publisher=

    work page 1957

  40. [40]

    Canadian Journal of mathematics , volume=

    Paths, trees, and flowers , author=. Canadian Journal of mathematics , volume=. 1965 , publisher=

    work page 1965

  41. [41]

    European Journal of Operational Research , volume=

    The late acceptance hill-climbing heuristic , author=. European Journal of Operational Research , volume=. 2017 , publisher=

    work page 2017

  42. [42]

    and Meunier, F

    Guyon, J. and Meunier, F. and Ben Salem, A. and Buchholtzer, T. and Tanr\'e, M. , year =. Drawing and scheduling the

    work page

  43. [43]

    Ranking matters: Does the new format select the best teams for the knockout phase in the

    Csat. Ranking matters: Does the new format select the best teams for the knockout phase in the. International Journal of Sports Science & Coaching , volume=. 2025 , publisher=

    work page 2025

  44. [44]

    American Journal of Computational Mathematics , volume=

    An Integer Programming Approach for Scheduling a Professional Sports League , author=. American Journal of Computational Mathematics , volume=. 2024 , publisher=

    work page 2024

  45. [45]

    Operations Research Perspectives , volume=

    The irace package: Iterated racing for automatic algorithm configuration , author=. Operations Research Perspectives , volume=. 2016 , publisher=

    work page 2016

  46. [46]

    Discrete Applied Mathematics , volume=

    Premature sets of l-factors or how not to schedule round robin tournaments , author=. Discrete Applied Mathematics , volume=

    work page

  47. [47]

    AUSTRALASIAN JOURNAL OF COMBINATORICS , volume=

    On the structure of graphs having a unique k-factor , author=. AUSTRALASIAN JOURNAL OF COMBINATORICS , volume=

    work page

  48. [48]

    , author=

    Short cycles in directed graphs. , author=. Journal of Combinatorial Theory , volume=

    work page

  49. [49]

    International Transactions in Operational Research , volume=

    Sports scheduling: Problems and applications , author=. International Transactions in Operational Research , volume=. 2012 , publisher=

    work page 2012

  50. [50]

    International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=

    Approximating maximum edge coloring in multigraphs , author=. International Workshop on Approximation Algorithms for Combinatorial Optimization , pages=. 2002 , organization=

    work page 2002

  51. [51]

    ACM Transactions on Algorithms (TALG) , volume=

    An asymptotic approximation scheme for multigraph edge coloring , author=. ACM Transactions on Algorithms (TALG) , volume=. 2008 , publisher=

    work page 2008

  52. [52]

    International Conference on Advanced Information Networking and Applications , pages=

    Fixed-parameter tractability for branchwidth of the maximum-weight edge-colored subgraph problem , author=. International Conference on Advanced Information Networking and Applications , pages=. 2024 , organization=

    work page 2024

  53. [53]

    Discrete Applied Mathematics , volume=

    Approximating the maximum 2-and 3-edge-colorable subgraph problems , author=. Discrete Applied Mathematics , volume=. 2009 , publisher=

    work page 2009

  54. [54]

    Discrete Mathematics , volume=

    Approximating the maximum 3-edge-colorable subgraph problem , author=. Discrete Mathematics , volume=. 2009 , publisher=

    work page 2009

  55. [55]

    Discrete Mathematics , volume=

    Alternating cycles and paths in edge-coloured multigraphs: a survey , author=. Discrete Mathematics , volume=. 1997 , publisher=

    work page 1997

  56. [56]

    Journal of Combinatorial Theory, Series B , volume=

    Alternating cycles in edge-partitioned graphs , author=. Journal of Combinatorial Theory, Series B , volume=. 1983 , publisher=

    work page 1983

  57. [57]

    European journal of combinatorics , volume=

    Equitable coloring and the maximum degree , author=. European journal of combinatorics , volume=. 1994 , publisher=

    work page 1994

  58. [58]

    Discrete Applied Mathematics , volume=

    Break minimization in incomplete round-robin tournaments , author=. Discrete Applied Mathematics , volume=. 2026 , publisher=

    work page 2026

  59. [59]

    Mathematical Programming , volume=

    Diverse collections in matroids and graphs , author=. Mathematical Programming , volume=. 2024 , publisher=

    work page 2024

  60. [60]

    Computers & Operations Research , volume=

    A new neighborhood structure for round robin scheduling problems , author=. Computers & Operations Research , volume=. 2016 , publisher=

    work page 2016

  61. [61]

    2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=

    Minimum weight cycles and triangles: Equivalences and algorithms , author=. 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science , pages=. 2011 , organization=

    work page 2011

  62. [62]

    Algorithms , volume=

    Introduction to reconfiguration , author=. Algorithms , volume=. 2018 , publisher=

    work page 2018

  63. [63]

    From groups to a single league: evaluating competitiveness in the

    Karel Devriesere and Dries Goossens and Frits Spieksma , journal =. From groups to a single league: evaluating competitiveness in the. 2026 , volume=

    work page 2026

  64. [64]

    Computers & Operations Research , volume=

    A multi-neighborhood hybrid approach for the integrated healthcare timetabling competition 2024 , author=. Computers & Operations Research , volume=. 2026 , publisher=

    work page 2024

  65. [65]

    Operations research , volume=

    Scheduling a major college basketball conference , author=. Operations research , volume=. 1998 , publisher=

    work page 1998

  66. [66]

    Operations research , volume=

    Scheduling a major college basketball conference—revisited , author=. Operations research , volume=. 2001 , publisher=

    work page 2001