New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918256063807488 |
|---|---|
| author | Liu, Bowen |
| author_facet | Liu, Bowen |
| contents | The score set of a tournament is defined as the set of its distinct out-degrees. In 1978, Reid proposed the conjecture that for any set of nonnegative integers $D$, there exists a tournament $T$ with a degree set $D$. In 1989, Yao presented an arithmetical proof of the conjecture, but a general polynomial-time construction algorithm is not known. This paper proposes a necessary and sufficient condition and a separate necessary condition, based on the existing Landau's theorem for the problem of reconstructing score sequences from score sets of tournament graphs. The necessary condition introduces a structured set that enables the use of group-theoretic techniques, offering not only a framework for solving the reconstruction problem but also a new perspective for approaching similar problems. In particular, the same theoretical approach can be extended to reconstruct valid score sets given constraints on the frequency of distinct scores in tournaments. Based on these conditions, we have developed three algorithms that demonstrate the practical utility of our framework: a polynomial-time algorithm and a scalable algorithm for reconstructing score sequences, and a polynomial-time network-building method that finds all possible score sequences for a given score set. Moreover, the polynomial-time algorithm for reconstructing the score sequence of a tournament for a given score set can be used to verify Reid's conjecture. These algorithms have practical applications in sports analysis, ranking prediction, and machine learning tasks such as learning-to-rank models and data imputation, where the reconstruction of partial rankings or sequences is essential for recommendation systems and anomaly detection. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_16961 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets Liu, Bowen Data Structures and Algorithms Combinatorics 68Q25, 90C27, 68W01 The score set of a tournament is defined as the set of its distinct out-degrees. In 1978, Reid proposed the conjecture that for any set of nonnegative integers $D$, there exists a tournament $T$ with a degree set $D$. In 1989, Yao presented an arithmetical proof of the conjecture, but a general polynomial-time construction algorithm is not known. This paper proposes a necessary and sufficient condition and a separate necessary condition, based on the existing Landau's theorem for the problem of reconstructing score sequences from score sets of tournament graphs. The necessary condition introduces a structured set that enables the use of group-theoretic techniques, offering not only a framework for solving the reconstruction problem but also a new perspective for approaching similar problems. In particular, the same theoretical approach can be extended to reconstruct valid score sets given constraints on the frequency of distinct scores in tournaments. Based on these conditions, we have developed three algorithms that demonstrate the practical utility of our framework: a polynomial-time algorithm and a scalable algorithm for reconstructing score sequences, and a polynomial-time network-building method that finds all possible score sequences for a given score set. Moreover, the polynomial-time algorithm for reconstructing the score sequence of a tournament for a given score set can be used to verify Reid's conjecture. These algorithms have practical applications in sports analysis, ranking prediction, and machine learning tasks such as learning-to-rank models and data imputation, where the reconstruction of partial rankings or sequences is essential for recommendation systems and anomaly detection. |
| title | New Theoretical Insights and Algorithmic Solutions for Reconstructing Score Sequences from Tournament Score Sets |
| topic | Data Structures and Algorithms Combinatorics 68Q25, 90C27, 68W01 |
| url | https://arxiv.org/abs/2512.16961 |