  The \emph{$k$-restricted edge-connectivity} of a graph $G$, denoted by
$\lambda_k(G)$, is defined as the minimum size of an edge set whose removal
leaves exactly two connected components each containing at least $k$ vertices.
This graph invariant, which can be seen as a generalization of a minimum
edge-cut, has been extensively studied from a combinatorial point of view.
However, very little is known about the complexity of computing $\lambda_k(G)$.
Very recently, in the parameterized complexity community the notion of
\emph{good edge separation} of a graph has been defined, which happens to be
essentially the same as the $k$-restricted edge-connectivity. Motivated by the
relevance of this invariant from both combinatorial and algorithmic points of
view, in this article we initiate a systematic study of its computational
complexity, with special emphasis on its parameterized complexity for several
choices of the parameters. We provide a number of NP-hardness and W[1]-hardness
results, as well as FPT-algorithms.
