Systems of distant representatives Original Research Article

We introduce a new notion of Systems of Distant Representatives of families of subsets of a metric space. We are in particular interested in the computational complexity of deciding the existence of such systems, for different distance parameters and for various metric spaces. The problem contains as a subproblem the well known polynomial time solvable problem of Systems of Distinct Representatives (for discrete metric and distance parameter 1). We prove several NP-hardness results, e.g., for discrete metric and distance parameter 2, or for Euclidean metric spaces. We also show a direct connection to practically motivated and previously studied problems such as scheduling, distance constrained graph labeling, map labeling, disjoint representatives of hypergraphs and independent sets in graphs. Finally, we mention our original motivation for studying distant representatives which comes from the distance constrained graph labeling and our complexity results imply a significant difference in the computational complexity of image-labeling of trees for image and image.