• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book

Computing and Combinatorics 25th International Conference, COCOON 2019, Xi'an, China, July 29–31, 2019, Proceedings

Vol. 11653: Lecture Notes in Computer Science. Springer, 2019.
Academic editor: D. Du.

In this paper, we study the Maximum Happy Vertices and the Maximum Happy Edges problems (MHV and MHE for short). Very recently, the problems attracted a lot of attention and were studied in Agrawal ’17, Aravind et al. ’16, Choudhari and Reddy ’18, Misra and Reddy ’17. 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 ’17), exponential lower bounds under the Set Cover Conjecture and the Exponential Time Hypothesis, and inapproximability results. Moreover, we present an O∗(ℓk)O∗(ℓk) randomized algorithm for MHV and an O∗(2k)O∗(2k) algorithm for MHE, where ℓℓ is the number of colors used and k is the number of required happy vertices or edges. These algorithms cannot be improved to subexponential taking proved lower bounds into account.

Chapters
Computing and Combinatorics 25th International Conference, COCOON 2019, Xi'an, China, July 29–31, 2019, Proceedings