Parameterized Complexity of Happy Coloring Problems

In a vertex-colored graph, an edge is emph{happy} if its endpoints have the same color. Similarly, a vertex is emph{happy} if all its incident edges are happy. Motivated by the computation of homophily in social networks, we consider the algorithmic aspects of the following probHappyEdges (probkMHE) problem: given a partially $k$-colored graph $G$ and an integer $ell$, find an extended full $k$-coloring of $G$ making at least $ell$ edges happy. When we want to make $ell$ vertices happy on the same input, the problem is known as probHappyVertices (probkMHV). We perform an extensive study into the complexity of the problems, particularly from a parameterized viewpoint. For every $k geq 3$, we prove both problems can be solved in time $2^n n^{O(1)}$. Moreover, by combining this result with a linear vertex kernel of size $(k+ell)$ for probkMHE, we show that the edge-variant can be solved in time $2^ell n^{O(1)}$. In contrast, we prove that the vertex-variant remains W-hard for the natural parameter~$ell$. However, the problem does admit a kernel with $O(k^2 ell^2)$ vertices for the combined parameter $k+ell$. From a structural perspective, we show both problems are fixed-parameter tractable for treewidth and neighborhood diversity, which can both be seen as sparsity and density measures of a graph. Finally, we extend the known $NP$-completeness results of the problems by showing they remain hard on bipartite graphs and split graphs. On the positive side, we show the vertex-variant can be solved optimally in polynomial-time for cographs.