Parameterized complexity of happy coloring problems

摘要

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 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. (C) 2020 Elsevier B.V. All rights reserved.