2026-09-21T10:00:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27292 2026-09-05T20:17:54Z ddc:004 open_access

The Power of the Score Sequence of a Tournament Ghosh, Prantar Kuchlous, Sahil Mehra, Shravan Mukhopadhyay, Sagnik tournaments score sequence cycle reversal streaming algorithms graph connectivity cut queries min-cut 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. 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 new bounds improving the state of the art. Specifically, our polynomial-time algorithms for almost-tournaments improve upon the exponential-time algorithms of Ghosh and Kuchlous and have much simpler analysis. The said 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. In particular, this gives us an O(n²)-cut-query algorithm to solve directed minimum cut on n-node graphs in polynomial time, a significant result that has been observed in the literature but not concretely stated in this form. Our results also unveil interesting general connections between two well-studied sublinear models for graph problems: semi-streaming and cut-query. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Prantar Ghosh and Sahil Kuchlous and Shravan Mehra and Sagnik Mukhopadhyay 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.156 urn:nbn:de:0030-drops-272928 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.156 eng https://creativecommons.org/licenses/by/4.0/legalcode