Parameterized complexity of happy coloring problems

Abstract In a vertex-colored graph, an edge is happy if its endpoints have the same color. Similarly, a vertex is 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 Maximum Happy Edges ( k -MHE ) problem: given a partially k-colored graph G and an integer l, find an extended full k-coloring of G making at least l edges happy. When we want to make l vertices happy on the same input, the problem is known as Maximum Happy Vertices ( k -MHV ). We perform an extensive study into the complexity of the problems, particularly from a parameterized viewpoint. For every k ≥ 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 + l ) for k -MHE , we show that the edge-variant can be solved in time 2 l n O ( 1 ) . In contrast, we prove that the vertex-variant remains W[1] -hard for the natural parameter l. However, the problem does admit a kernel with O ( k 2 l 2 ) vertices for the combined parameter k + l . 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 -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.