  We investigate the parameterized complexity of several problems formalizing
cluster identification in graphs. In other words we ask whether a graph
contains a large enough and sufficiently connected subgraph. We study here
three relaxations of CLIQUE: $s$-CLUB and $s$-CLIQUE, in which the relaxation
is focused on the distances in respectively the cluster and the original graph,
and $\gamma$-COMPLETE SUBGRAPH in which the relaxation is made on the minimal
degree in the cluster. As these three problems are known to be NP-hard, we
study here their parameterized complexities. We prove that $s$-CLUB and
$s$-CLIQUE are NP-hard even restricted to graphs of degeneracy $\le 3$ whenever
$s \ge 3$, and to graphs of degeneracy $\le 2$ whenever $s \ge 5$, which is a
strictly stronger result than its W[1]-hardness parameterized by the
degeneracy. We also obtain that these problems are solvable in polynomial time
on graphs of degeneracy $1$. Concerning $\gamma$-COMPLETE SUBGRAPH, we prove
that it is W[1]-hard parameterized by both the degeneracy, which implies the
W[1]-hardness parameterized by the number of vertices in the
$\gamma$-complete-subgraph, and the number of elements outside the
$\gamma$-complete subgraph.
