Seminars

View all Seminars  |  Download ICal for this event

The Power of the Score Sequence of a Tournament

Series: Bangalore Theory Seminars

Speaker: Prantar Ghosh, Tennessee Tech University

Date/Time: Jun 17 11:00:00

Location: CSA Auditorium, (Room No. 104, Ground Floor)

Abstract:
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.

Microsoft teams link:

Link

We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan