Is the following problem NP-hard?Given a set of $N$ real numbers (targets) $x_1,\dotsc,x_N$ and a trident defined by two distances $a$, $b$ from the center of the trident, what is the minimum number $K$ of positions $p_1,\dotsc,p_K$ of the trident to cover all targets, i.e.$$ \bigcup_{k=1}^K \{p_k-a,p_k,p_k+b\} \supseteq \{x_1,\dotsc,x_N\}.$$Obviously, this is a special case of the set cover problem: Considering all sets $\{p_k-a,p_k,p_k+b\}$, with $p_k\in\{x_n+t\mid n\in\{1,\dotsc,N\}, t\in\{a,0,-b\}\}$ representing all relevant potential positions, we look for the minimum number of sets covering the universe $\{x_1,\dotsc,x_N\}$. Equivalently, we can represent the problem as a bipartite graph of position and target nodes and consider the hitting set problem.Note that the problem is not NP-hard if the trident loses one of its jags: Then each target can be covered from 2 positions and each position covers at most 2 targets, so the corresponding bipartite graph of potential positions and targets is a union of paths. In each path it is easy to determine a minimal hitting set (namely, the inner position nodes).But is the trident case NP-hard?
NP-hardness of a Set Cover specialization
cc.complexity theory;np hardness;set cover