Lower bounds for the happy coloring problems

In this paper, we study the and the problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal '18, Aravind et al. '16, Choudhari and Reddy '18, Misra and Reddy '18. Main focus of our work is lower bounds on the computational complexity of these problems. Established lower bounds can be divided into the following groups: NP-hardness of the above guarantee parameterization, kernelization lower bounds (answering questions of Misra and Reddy '18), exponential lower bounds under the and the , and inapproximability results. Moreover, we present an randomized algorithm for MHV and an algorithm for MHE, where is the number of colors used and is the number of required happy vertices or edges. These algorithms cannot be improved to subexponential taking proved lower bounds into account.