Abstract: We investigate the maximum happy vertices (MHV) problem and its complement, the minimum unhappy vertices (MUHV) problem. In order to design better approximation algorithms, we introduce the supermodular and submodular multi-labeling (Sup-ML and Sub-ML) problems and show that MHV and MUHV are special cases of Sup-ML and Sub-ML, respectively, by rewriting the objective functions as set functions. The convex relaxation on the Lovász extension, originally presented for the submodular multi-partitioningproblem,canbeextendedfortheSub-MLproblem,therebyproving that Sub-ML (Sup-ML, respectively) can be approximated within a factor of 2-2/k (2/k, respectively), where k is the number of labels. These general results imply that MHV and MUHV can also be approximated within factors of 2/k and 2-2/k, respectively, using the same approximation algorithms. For the MUHV problem, we also show that it is approximation-equivalent to the hypergraph multiway cut problem; thus, MUHV is Unique Games-hard to achieve a (2-2/k-ε)-approximation, for any ε > 0. For the MHV problem, the 2/k-approximation improves the previous best approximation ratio max{1/k, 1/Δ + 1/g(Δ) }, where Δ is the maximum vertex degree of the input graph and g(Δ)=(√Δ+√Δ+1)² Δ > 4Δ². We also show that an existing LP relaxation for MHV is the same as the concave relaxation on the Lovász extension for Sup-ML; we then prove an upper bound of 2/k on the integrality gap of this LP relaxation, which suggests that the 2/k-approximation is the best possible based on this LP relaxation. Lastly, we prove that it is Unique Games-hard to approximate the MHV problem within a factor of Ω(log² k/k).

Key words: Vertex happiness, Multi-labeling, Submodular/supermodular set function, Approximation algorithm, Polynomial-time reduction, Integrality gap