# The parameterized complexity of happy colorings

 dc.contributor.author Misra, Neeldhara dc.contributor.author Reddy, I. Vinod dc.date.accessioned 2017-09-02T10:16:09Z dc.date.available 2017-09-02T10:16:09Z dc.date.issued 2017-08 dc.identifier.citation Misra, Neeldhara and Reddy, I. Vinod, “The parameterized complexity of happy colorings”, arXiv, Cornell University Library, DOI: arXiv:1708.03853, Aug. 2017. en_US dc.identifier.uri https://arxiv.org/abs/1708.03853 dc.identifier.uri https://repository.iitgn.ac.in/handle/123456789/3122 dc.description.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. en_US 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. dc.description.statementofresponsibility by Neeldhara Misra and I. Vinod Reddy dc.language.iso en_US en_US dc.publisher Cornell University Library en_US dc.title The parameterized complexity of happy colorings en_US dc.type Preprint en_US
﻿

## Files in this item

Files Size Format View

There are no files associated with this item.