  We study fundamental directed graph (digraph) problems in the streaming
model. An initial investigation by Chakrabarti, Ghosh, McGregor, and
Vorotnikova [SODA'20] on streaming digraphs showed that while most of these
problems are provably hard in general, some of them become tractable when
restricted to the well-studied class of tournament graphs where every pair of
nodes shares exactly one directed edge. Thus, we focus on tournaments and
improve the state of the art for multiple problems in terms of both upper and
lower bounds.
  Our primary upper bound is a deterministic single-pass semi-streaming
algorithm (using $\tilde{O}(n)$ space for $n$-node graphs, where $\tilde{O}(.)$
hides polylog$(n)$ factors) for decomposing a tournament into strongly
connected components (SCC). it improves upon the previously best-known
algorithm by Baweja, Jia, and Woodruff [ITCS'22] in terms of both space and
passes: for $p\geq 1$, they used $(p+1)$-passes and
$\tilde{O}(n^{1+1/p})$-space. We further extend our algorithm to digraphs that
are close to tournaments and establish tight bounds demonstrating that the
problem's complexity grows smoothly with the "distance" from tournaments.
Applying our framework, we obtain improved tournament algorithms for
$s,t$-reachability, strong connectivity, Hamiltonian paths and cycles, and
feedback arc set.
  On the other hand, we prove the first $\Omega(n^2)$-space lower bounds for
this class, exhibiting that some well-studied problems -- such as (exact)
feedback arc set on tournaments (FAST) and $s,t$-distance -- remain hard here.
We obtain a generalized lower bound on space-approximation tradeoffs for FAST:
any single-pass $(1\pm \varepsilon)$-approximation algorithm requires
$\Omega(n/\sqrt{\varepsilon})$ space. As a whole, our collection of results
contributes significantly to the growing literature on streaming digraphs.
