  We revisit the complexity of the well-studied notion of Additively Separable
Hedonic Games (ASHGs). Such games model a basic clustering or coalition
formation scenario in which selfish agents are represented by the vertices of
an edge-weighted digraph $G=(V,E)$, and the weight of an arc $uv$ denotes the
utility $u$ gains by being in the same coalition as $v$. We focus on (arguably)
the most basic stability question about such a game: given a graph, does a Nash
stable solution exist and can we find it efficiently?
  We study the (parameterized) complexity of ASHG stability when the underlying
graph has treewidth $t$ and maximum degree $\Delta$. The current best FPT
algorithm for this case was claimed by Peters [AAAI 2016], with time complexity
roughly $2^{O(\Delta^5t)}$. We present an algorithm with parameter dependence
$(\Delta t)^{O(\Delta t)}$, significantly improving upon the parameter
dependence on $\Delta$ given by Peters, albeit with a slightly worse dependence
on $t$. Our main result is that this slight performance deterioration with
respect to $t$ is actually completely justified: we observe that the previously
claimed algorithm is incorrect, and that in fact no algorithm can achieve
dependence $t^{o(t)}$ for bounded-degree graphs, unless the ETH fails. This,
together with corresponding bounds we provide on the dependence on $\Delta$ and
the joint parameter establishes that our algorithm is essentially optimal for
both parameters, under the ETH.
  We then revisit the parameterization by treewidth alone and resolve a
question also posed by Peters by showing that Nash Stability remains strongly
NP-hard on stars under additive preferences. Nevertheless, we also discover an
island of mild tractability: we show that Connected Nash Stability is solvable
in pseudo-polynomial time for constant $t$, though with an XP dependence on $t$
which, as we establish, cannot be avoided.
