The Power of the Score Sequence of a Tournament
2026-07-16 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study problems on tournaments, which are special kinds of directed graphs, but only use the score sequence (number of incoming edges per vertex) to solve them. They provide a unified method to solve various problems like checking for cycles, connectivity, and ordering vertices, showing these solutions depend only on indegree information and remain unchanged if cycles are reversed. Their results also extend to more general directed graphs when combined with the underlying undirected structure. Additionally, they develop efficient algorithms for related problems in different computational models, some of which improve previous results.
tournamentscore sequenceindegreedirected graphstrong connectivitycycle reversaltopological sortinggraph algorithmscutwidthstreaming algorithms
Authors
Prantar Ghosh, Sahil Kuchlous, Shravan Mehra, Sagnik Mukhopadhyay
Abstract
What problems can one solve on a tournament if only its score sequence is known? Tournaments are oriented complete graphs that form an extensively-studied class of directed graphs (digraphs), both from combinatorial and algorithmic perspectives. Over the years, researchers have identified multiple classical digraph problems that can be solved on a tournament from only its score sequence (indegree sequence). These problems include acyclicity testing and topological sorting [Chakrabarti, Ghosh, McGregor, and Vorotnikova; SODA'20], $s,t$-reachability, strong connectivity, and decomposition into strongly connected components (SCC) [Ghosh and Kuchlous; ESA'24], and vertex-ordering problems such as cutwidth and optimal linear arrangement [Barbero, Paul, and Pilipczuk; ICALP'17]. These prior works showed the sufficiency of the score sequence by designing distinct algorithms for the individual problems. In this work, we give a simple unified framework that solves all these problems using only indegrees and, in fact, completely characterises the class of problems that is determined by the indegree information: problems whose answers are invariant under cycle reversals. This characterisation is a special case of a much more general result that we establish: for any arbitrary digraph, the knowledge of its skeleton (underlying undirected graph) and the vertex indegrees completely determines its properties that are invariant under cycle reversal. As a byproduct of our results, we obtain algorithms for a variety of connectivity-based, cut-based, and vertex-ordering problems on tournaments and ``almost tournaments'' in the streaming, the two-player communication, and the cut-query models of computation. Some of these algorithms match existing optimal bounds and others provide bounds improving the state of the art.