  We investigate the maximum happy vertices (MHV) problem and its complement,
the minimum unhappy vertices (MUHV) problem. We first show that the MHV and
MUHV problems are a special case of the supermodular and submodular
multi-labeling (Sup-ML and Sub-ML) problems, respectively, by re-writing the
objective functions as set functions. The convex relaxation on the Lov\'{a}sz
extension, originally presented for the submodular multi-partitioning (Sub-MP)
problem, can be extended for the Sub-ML problem, thereby proving that the
Sub-ML (Sup-ML, respectively) can be approximated within a factor of $2 -
\frac{2}{k}$ ($\frac{2}{k}$, respectively). These general results imply that
the MHV and the MUHV problems can also be approximated within $\frac{2}{k}$ and
$2 - \frac{2}{k}$, respectively, using the same approximation algorithms. For
MHV, this $\frac{2}{k}$-approximation algorithm improves the previous best
approximation ratio $\max \{\frac{1}{k}, \frac{1}{\Delta + 1}\}$, where
$\Delta$ is the maximum vertex degree of the input graph. We also show that an
existing LP relaxation is the same as the concave relaxation on the Lov\'{a}sz
extension for the Sup-ML problem; we then prove an upper bound of $\frac{2}{k}$
on the integrality gap of the LP relaxation. These suggest that the
$\frac{2}{k}$-approximation algorithm is the best possible based on the LP
relaxation. For MUHV, we formulate a novel LP relaxation and prove that it is
the same as the convex relaxation on the Lov\'{a}sz extension for the Sub-ML
problem; we then show a lower bound of $2 - \frac{2}{k}$ on the integrality gap
of the LP relaxation. Similarly, these suggest that the $(2 -
\frac{2}{k})$-approximation algorithm is the best possible based on the LP
relaxation. Lastly, we prove that this $(2 - \frac{2}{k})$-approximation is
optimal for the MUHV problem, assuming the Unique Games Conjecture.
