  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, find an extended full k-coloring of G maximizing
the number of happy edges. When we want to maximize the number of happy
vertices, the problem is known as Maximum Happy Vertices (k-MHV). We further
study the complexity of the problems and their weighted variants. For instance,
we prove that for every k >= 3, both problems are NP-complete for bipartite
graphs and k-MHV remains hard for split graphs. In terms of exact algorithms,
we show both problems can be solved in time O*(2^n), and give an even faster
O*(1.89^n)-time algorithm when k = 3. From a parameterized perspective, we give
a linear vertex kernel for Weighted k-MHE, where edges are weighted and the
goal is to obtain happy edges of at least a specified total weight. Finally, we
prove both problems are solvable in polynomial-time when the graph has bounded
treewidth or bounded neighborhood diversity.
