New answers tagged np-hardness
3
Even computing a maximum independent set of unit axis-parallel squares is known to be np-hard:
https://www.sciencedirect.com/science/article/pii/0020019081901113?via%3Dihub
Since coloring is a "harder" problem, it should also be NP-hard. A constant approximation follows as if a point is covered by $k$ squares, then the chromatic number is at least $...
6
NP-hardness is proved by Roth and Viswanathan in the paper On the hardness of decoding the gale-berlekamp code
answered Jun 27 at 14:14
Kristoffer Arnsfelt Hansen
4,0902 gold badges23 silver badges34 bronze badges
Top 50 recent answers are included
