  Our work concerns algorithms for an unweighted variant of Maximum Flow. In
the All-Pairs Connectivity (APC) problem, we are given a graph $G$ on $n$
vertices and $m$ edges, and are tasked with computing the maximum number of
edge-disjoint paths from $s$ to $t$ (equivalently, the size of a minimum
$(s,t)$-cut) in $G$, for all pairs of vertices $(s,t)$. Although over
undirected graphs APC can be solved in essentially optimal $n^{2+o(1)}$ time,
the true time complexity of APC over directed graphs remains open: this problem
can be solved in $\tilde{O}(m^\omega)$ time, where $\omega \in [2, 2.373)$ is
the exponent of matrix multiplication, but no matching conditional lower bound
is known.
  We study a variant of APC called the $k$-Bounded All Pairs Connectivity
($k$-APC) problem. In this problem, we are given an integer $k$ and graph $G$,
and are tasked with reporting the size of a minimum $(s,t)$-cut only for pairs
$(s,t)$ of vertices with a minimum cut size less than $k$ (if the minimum
$(s,t)$-cut has size at least $k$, we just report it is "large" instead of
computing the exact value).
  We present an algorithm solving $k$-APC in directed graphs in
$\tilde{O}((kn)^\omega)$ time. This runtime is $\tilde O(n^\omega)$ for all $k$
polylogarithmic in $n$, which is essentially optimal under popular conjectures
from fine-grained complexity. Previously, this runtime was only known for $k\le
2$ [Georgiadis et al., ICALP 2017].
  We also study a variant of $k$-APC, the $k$-Bounded All-Pairs Vertex
Connectivity ($k$-APVC) problem, which considers internally vertex-disjoint
paths instead of edge-disjoint paths. We present an algorithm solving $k$-APVC
in directed graphs in $\tilde{O}(k^2n^\omega)$ time. Previous work solved an
easier version of the $k$-APVC problem in $\tilde O((kn)^\omega)$ time [Abboud
et al, ICALP 2019].
