The parameterized complexity of happy colorings
Date Issued
2017-08-01
Abstract
Consider a graph G=(V,E) and a coloring c of vertices with colors from [?]. A vertex v is said to be happy with respect to c if c(v)=c(u) for all neighbors u of v. Further, an edge (u,v) is happy if c(u)=c(v). Given a partial coloring c of V, the Maximum Happy Vertex (Edge) problem asks for a total coloring of V extending c to all vertices of V that maximises the number of happy vertices (edges). Both problems are known to be NP-hard in general even when ?=3, and is polynomially solvable when ?=2. In [IWOCA 2016] it was shown that both problems are polynomially solvable on trees, and for arbitrary k, it was shown that MHE is \NPH{} on planar graphs and is \FPT{} parameterized by the number of precolored vertices and branchwidth.
We continue the study of this problem from a parameterized prespective. Our focus is on both structural and standard parameterizations. To begin with, we establish that the problems are \FPT{} when parameterized by the treewidth and the number of colors used in the precoloring, which is a potential improvement over the total number of precolored vertices. Further, we show that both the vertex and edge variants of the problem is \FPT{} when parameterized by vertex cover and distance-to-clique parameters. We also show that the problem of maximizing the number of happy edges is \FPT{} when parameterized by the standard parameter, the number of happy edges. We show that the maximum happy vertex (edge) problem is \NPH{} on split graphs and bipartite graphs and polynomially solvable on cographs.
We continue the study of this problem from a parameterized prespective. Our focus is on both structural and standard parameterizations. To begin with, we establish that the problems are \FPT{} when parameterized by the treewidth and the number of colors used in the precoloring, which is a potential improvement over the total number of precolored vertices. Further, we show that both the vertex and edge variants of the problem is \FPT{} when parameterized by vertex cover and distance-to-clique parameters. We also show that the problem of maximizing the number of happy edges is \FPT{} when parameterized by the standard parameter, the number of happy edges. We show that the maximum happy vertex (edge) problem is \NPH{} on split graphs and bipartite graphs and polynomially solvable on cographs.