The Problem of Compatible Representatives
Donald E. Knuth, Arvind U. Raghunathan · SIAM Journal on Discrete Mathematics · 1992
This paper attaches a name to a natural class of combinatorial problems and points out that the class includes many important special cases. One special case, a simple problem of placing nonoverlapping labels on a rectangular map, is shown to be NP-complete.