Parameterized complexity of happy coloring problems

• Published in: Theoretical computer science 2020-10, Vol.835, p.58-81
• Main Authors: Agrawal, Akanksha, Aravind, N.R., Kalyanasundaram, Subrahmanyam, Kare, Anjeneya Swami, Lauri, Juho, Misra, Neeldhara, Reddy, I. Vinod
• Format: Article
• Language: English
• Subjects: Computational complexity; Happy coloring; Parameterized complexity
• ISSN: 0304-3975; 1879-2294
• DOI: 10.1016/j.tcs.2020.06.002

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 ℓ, find an extended full k-coloring of G making at least ℓ edges happy. When we want to make ℓ 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 2nnO(1). Moreover, by combining this result with a linear vertex kernel of size (k+ℓ) for k-MHE, we show that the edge-variant can be solved in time 2ℓnO(1). In contrast, we prove that the vertex-variant remains W[1]-hard for the natural parameter ℓ. However, the problem does admit a kernel with O(k2ℓ2) vertices for the combined parameter k+ℓ. 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.