The parameterized complexity of happy colorings

Show simple item record

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. 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. en_US
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.

This item appears in the following Collection(s)

Show simple item record

Search Digital Repository


Browse

My Account