  In the Colored Clustering problem, one is asked to cluster edge-colored
(hyper-)graphs whose colors represent interaction types. More specifically, the
goal is to select as many edges as possible without choosing two edges that
share an endpoint and are colored differently. Equivalently, the goal can also
be described as assigning colors to the vertices in a way that fits the
edge-coloring as well as possible. As this problem is NP-hard, we build on
previous work by studying its parameterized complexity. We give a $2^{\mathcal
O(k)} \cdot n^{\mathcal O(1)}$-time algorithm where $k$ is the number of edges
to be selected and $n$ the number of vertices. We also prove the existence of a
problem kernel of size $\mathcal O(k^{5/2} )$, resolving an open problem posed
in the literature. We consider parameters that are smaller than $k$, the number
of edges to be selected, and $r$, the number of edges that can be deleted. Such
smaller parameters are obtained by considering the difference between $k$ or
$r$ and some lower bound on these values. We give both algorithms and lower
bounds for Colored Clustering with such parameterizations. Finally, we settle
the parameterized complexity of Colored Clustering with respect to structural
graph parameters by showing that it is $W[1]$-hard with respect to both vertex
cover number and tree-cut width, but fixed-parameter tractable with respect to
slim tree-cut width.
