  We consider the fundamental problems of determining the rooted and global
edge and vertex connectivities (and computing the corresponding cuts) in
directed graphs. For rooted (and hence also global) edge connectivity with
small integer capacities we give a new randomized Monte Carlo algorithm that
runs in time $\tilde{O}(n^2)$. For rooted edge connectivity this is the first
algorithm to improve on the $\Omega(n^3)$ time bound in the dense-graph
high-connectivity regime. Our result relies on a simple combination of sampling
coupled with sparsification that appears new, and could lead to further
tradeoffs for directed graph connectivity problems.
  We extend the edge connectivity ideas to rooted and global vertex
connectivity in directed graphs. We obtain a $(1 + \epsilon)$-approximation for
rooted vertex connectivity in $\tilde{O}(nW/\epsilon)$ time where $W$ is the
total vertex weight (assuming integral vertex weights); in particular this
yields an $\tilde{O}(n^2/\epsilon)$ time randomized algorithm for unweighted
graphs. This translates to a $\tilde{O}(\kappa nW)$ time exact algorithm where
$\kappa$ is the rooted connectivity. We build on this to obtain similar bounds
for global vertex connectivity.
  Our results complement the known results for these problems in the low
connectivity regime due to work of Gabow [9] for edge connectivity from 1991,
and the very recent work of Nanongkai et al. [24] and Forster et al. [7] for
vertex connectivity.
