No-Rainbow Problem is NP-Hard.
Dmitriy N. Zhuk · arXiv (Cornell University) · 2020
Surjective Constraint Satisfaction Problem (SCSP) is the problem of deciding whether there exists a surjective assignment to a set of variables subject to some specified constraints. In this paper we show that one of the most popular variants of the SCSP, called No-Rainbow Problem, is NP-Hard.