A tournament is a directed graph where each pair of vertices shares exactly one directed edge. It might model a round-robin tournament where every game has a winner and a loser (no draws). The score sequence of a tournament is then given by its sequence of vertex indegrees, i.e., the "scores" of the players. Over the years, researchers have shown that the score sequence suffices to solve multiple fundamental problems on tournaments, such as acyclicity testing, topological sorting, optimal linear arrangement, and cutwidth. In this talk, I shall first show a surprising power of the sequence: it completely determines reachability between two nodes, strong connectivity, and in general, the decomposition of a tournament into strongly connected components (SCC). This makes one wonder: can we characterise the class of problems determined by the score sequence of a tournament? The talk will answer this question in the affirmative to show that the class contains precisely all problems whose answers are invariant under cycle reversals. The said characterization is a special case of a much more general result: 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 these results, one can obtain optimal algorithms (up to a logarithmic factor) 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.
This is based on a joint work with Sahil Kuchlous (ESA'24) and a work under submission with Sahil, Sagnik Mukhopadhyay, and Shravan Mehra.
