Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Parameterized Complexity of Happy Colorings   Consider a graph $G = (V,E)$ and a coloring $c$ of vertices with colors from
$[\ell]$. 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 $\ell = 3$, and is polynomially solvable when
$\ell = 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.

17
The categories of this paper are: q-fin
11
The categories of this paper are: hep-lat
13
The categories of this paper are: quant-ph
5
The categories of this paper are: gr-qc
4
The categories of this paper are: cond-mat
29
The categories of this paper are: funct-an
33
The categories of this paper are: plasm-ph
12
The categories of this paper are: nucl-th
31
The categories of this paper are: ao-sci
37
The categories of this paper are: supr-con
28
The categories of this paper are: alg-geom
25
The categories of this paper are: patt-sol
22
The categories of this paper are: chao-dyn
15
The categories of this paper are: nucl-ex
18
The categories of this paper are: econ
24
The categories of this paper are: dg-ga