The parameterized complexity of happy colorings

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Consider a graph

G = (V, E)

and a coloring

c

of vertices with colors from

[e l l]

. 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

e l l = 3

, and is polynomially solvable when

e l l = 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.

Recommendations

Cited in

(8)

This page was built for publication: The parameterized complexity of happy colorings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1642692)