- Algorithms for Streaming Tournaments
- Project Year:
2023
- REU Student (s):
Sahil Kuchlous | Harvard University MA
- Student 1 Institution:
Harvard University
- Project Mentor:
Prantar Ghosh
- Project Mentor Area:
DIMACS
- Project Abstract:
We present the first (non-trivial) Ω(n2) lower bound on streaming algorithms for tournaments on n vertices, demonstrating that (exactly) solving the minimum feedback arc set (FAS) problem on tournaments is hard. This complements recent work on upper bounds for the (approximate) FAS problem on tournaments, and shows that even though acyclicity testing can be solved in near-linear memory on tournaments, some important related questions remain hard. We also investigate a number of fundamental graph problems on tournaments: we prove new upper and lower bounds for s-t distance and reachability, and settle the streaming complexity of acyclicity testing. Finally, we settle the streaming complexity of sink finding in general directed graphs.
