Kernelization for Maximum Happy Vertices Problem

摘要

The homophyly phenomenon is very common in social networks. The Maximum Happy Vertices (MHV) is a newly proposed problem related to homophyly phenomenon. Given a graph G = (V, E) and a vertex coloring of G, we say that a vertex v is happy if v shares the same color with all its neighbors, and unhappy, otherwise, and that an edge e is happy, if its two endpoints have the same color, and unhappy, otherwise. Given a partial vertex coloring of G with k number of different colors, the k-MHV problem is to color all the remaining vertices such that the number of happy vertices is at least l. We study k-MHV from the parameterized algorithm perspective; we prove that k-MHV has an exponential kernel of 2~(kl+l) + kl + k + I on general graph. For planar graph, we get a much better polynomial kernel of 7(kl +l) + k - 10.