  Consider the following "local" cut-detection problem in a directed graph: We
are given a seed vertex $x$ and need to remove at most $k$ edges so that at
most $\nu$ edges can be reached from $x$ (a "local" cut) or output $\bot$ to
indicate that no such cut exists. If we are given query access to the input
graph, then this problem can in principle be solved without reading the whole
graph and with query complexity depending on $k$ and $\nu$. In this paper we
consider a slack variant of this problem where, when such a cut exists, we can
output a cut with up to $O(k\nu)$ edges reachable from $x$.
  We present a simple randomized algorithm spending $O(k^2\nu)$ time and
$O(k\nu)$ queries for the above variant, improving in particular a previous
time bound of $O(k^{O(k)}\nu)$ by Chechik et al. [SODA '17]. We also extend our
algorithm to handle an approximate variant. We demonstrate that these local
algorithms are versatile primitives for designing substantially improved
algorithms for classic graph problems by providing the following three
applications. (Throughout, $\tilde O(T)$ hides $\operatorname{polylog}(T)$.)
(1) A randomized algorithm for the classic $k$-vertex connectivity problem that
takes near-linear time when $k=O(\operatorname{polylog}(n))$, namely $\tilde
O(m+nk^3)$ time in undirected graphs. For directed graphs our $\tilde
O(mk^2)$-time algorithm is near-linear when $k=O(\operatorname{polylog}(n))$.
Our techniques also yield an improved approximation scheme. (2) Property
testing algorithms for $k$-edge and -vertex connectivity with query
complexities that are near-linear in $k$, exponentially improving the
state-of-the-art. This resolves two open problems, one by Goldreich and Ron
[STOC '97] and one by Orenstein and Ron [Theor. Comput Sci. '11]. (3) A faster
algorithm for computing the maximal $k$-edge connected subgraphs, improving
prior work of Chechik et al. [SODA '17].
