Selecting and covering colored points

Let [Formula presented] be a set of colored objects, where the color of an object is an integer between 1 and [Formula presented]. Let [Formula presented] be the partition of [Formula presented] into color classes, i.e., the set [Formula presented] consists of all objects in [Formula presented] colored [Formula presented]. We study two families of problems on color classes, namely, rainbow problems and covering problems where the covering objects have a certain property. The goal in a rainbow problem is to select an optimal rainbow, subject to the conditions of the problem, where a rainbow is a subset of [Formula presented] that contains at most one object from each color class. For example, in the problem known as rainbow minmax gap the color classes are pairs of points on the [Formula presented]-axis, and one needs to select exactly one point from each color class (i.e., a complete rainbow), such that the maximum distance between a pair of consecutive selected points is minimized. This problem was studied by Consuegra and Narasimhan, who left the question of its complexity unresolved. We prove that it is NP-hard. For our proof we obtain the following auxiliary result. A 3-SAT formula is an LSAT formula if each clause (viewed as a set of literals) intersects at most one other clause, and, moreover, if two clauses intersect, then they have exactly one literal in common. We prove that the problem of deciding whether an LSAT formula is satisfiable or not is NP-complete. Using the LSAT result, we also prove that rainbow piercing and rainbow covering are NP-complete. In the covering problems that we consider, [Formula presented] is a set of points and only conflict-free objects are allowed, where an object is conflict free if it covers at most one point from each color class. The goal is to find a minimum-cardinality set of conflict-free objects that cover at least (or exactly) one point from each color class. We prove that problems in this family are NP-hard (or NP-complete) and present several constant-factor approximation algorithms.