Linear Time Algorithms for Happy Vertex Coloring Problems for Trees

Abstract

Given an undirected graph $G=(V,E)$ with $|V|=n$ and a vertex coloring, a vertex $v$ is happy if $v$ and all its neighbors have the same color. An edge is happy if its end vertices have the same color. Given a partial coloring of the vertices of the graph using $k$ colors, the Maximum Happy Vertices (also called $k$-MHV) problem asks to color the remaining vertices such that the number of happy vertices is maximized. The Maximum Happy Edges (also called $k$-MHE) problem asks to color the remaining vertices such that the number of happy edges is maximized. For arbitrary graphs, $k$-MHV and $k$-MHE are NP-Hard for $k \geq 3$. In this paper we study these problems for trees. For a fixed $k$ we present linear time algorithms for both the problems. In general, for any $k$ the proposed algorithms take $O(nk \log k)$ and $O(nk)$ time respectively.

Publication
Proceedings of the 27th International Workshop on Combinatorial Algorithms - IWOCA 2016, Helsinki, Finland
Date