  We study the {\em $k$-route} generalizations of various cut problems, the
most general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein we
have $r$ source-sink pairs and the goal is to delete a minimum-cost set of
edges to reduce the edge-connectivity of every source-sink pair to below $k$.
The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cut
problem ($k$-$(s,t)$-cut), are similarly defined. We present various
approximation and hardness results for these $k$-route cut problems that
improve the state-of-the-art for these problems in several cases. (i) For {\em
$k$-route multiway cut}, we devise simple, but surprisingly effective,
combinatorial algorithms that yield bicriteria approximation guarantees that
markedly improve upon the previous-best guarantees. (ii) For {\em $k$-route
multicut}, we design algorithms that improve upon the previous-best
approximation factors by roughly an $O(\sqrt{\log r})$-factor, when $k=2$, and
for general $k$ and unit costs and any fixed violation of the connectivity
threshold $k$. The main technical innovation is the definition of a new,
powerful \emph{region growing} lemma that allows us to perform region-growing
in a recursive fashion even though the LP solution yields a {\em different
metric} for each source-sink pair. (iii) We complement these results by showing
that the {\em $k$-route $s$-$t$ cut} problem is at least as hard to approximate
as the {\em densest-$k$-subgraph} (DkS) problem on uniform hypergraphs.
