We investigate the computation of minimum-cost spanning trees satisfying prescribed vertex degree constraints: Given a graph $G$ and a constraint function $D$, we ask for a (minimum-cost) spanning tree $T$ such that for each vertex $v$, $T$ achieves a degree specified by $D(v)$. Specifically, we consider three kinds of constraint functions ordered by their generality -- $D$ may either assign each vertex to a list of admissible degrees, an upper bound on the degrees, or a specific degree. Using a combination of novel techniques and state-of-the-art machinery, we obtain an almost-complete overview of the fine-grained complexity of these problems taking into account the most classical graph parameters of the input graph $G$. In particular, we present SETH-tight upper and lower bounds for these problems when parameterized by the pathwidth and cutwidth, an ETH-tight algorithm parameterized by the cliquewidth, and a nearly SETH-tight algorithm parameterized by treewidth. In order to obtain our upper bound for clique-width, we develop a novel technique of double representation through ``requirement shifting''. Using this technique, we also obtain an ETH-tight single-exponential XP algorithm for the Exact Leaf Spanning Tree problem parameterized by clique-width, which settles the final remaining open case for clique-width from the classical Cut and Count of Cygan et al. [FOCS 2011, TALG 2022]. This shows the versatility of our technique and its potential applicability to other problems as well. Additionally, in order to establish our lower and upper bounds we introduce a number of tools which may be of independent interest, including lazy coloring and ``asymptotic'' SETH-based reductions for structural parameters.

Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may look to add or delete few edges to uncover the cluster structure, or we may split vertices to separate the clusters from each other. Splitting a vertex v means to remove it and to add two new copies of v and to make each previous neighbor of v adjacent with at least one of the copies. In this work, we study underlying computational problems regarding the three angles to overlapping clusterings, in particular when the overlap is small. We show that the above-mentioned covering problem is NP -complete. We then make structural observations that show that the covering viewpoint and the vertex-splitting viewpoint are equivalent, yielding NP-hardness for the vertex-splitting problem. On the positive side, we show that splitting at most k vertices to obtain a cluster graph has a problem kernel with O ( k ) vertices. Finally, we observe that combining our hardness results with structural observations and a so-called critical-clique lemma yields a simple alternative NP-hardness proof for the Cluster Editing With Vertex Splitting problem, where we add or delete edges and split vertices to obtain a cluster graph.