- Algorithms for Streaming Tournaments
- Project Year:
2023
- REU Student (s):
Sahil Kuchlous | Harvard University MA
- Project Mentor (s) :
Prantar Ghosh - 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.
