Edit: I first misformulated my constraint (2), it is now corrected. I also added more information and examples.With some colleagues, studying some other algorithmic question, we were able to reduce our problem down to the following interesting problem, but we were not able to solve the question of its complexity. The problem is as follows.Instance: An integer $n$, an integer $k<n$, and a set $S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$ of $n$ pairs from the set $\{1,\ldots,n\}$.Question: Is there a set $S'\subseteq S$ of size $k$ such that for each element $i$ of $\{1,\ldots,n\}$:  (1) if $i<n$, the interval $[i,i+1]$ is included in some interval $[s_i,t_i]$ defined by a pair in $S'$, and(2) at least one of $i$, $i+1$ belongs to some pair of $S'$?  (2) $i$ belongs to some pair of $S'$.ExampleThe set $\{\{i,i+1\}~|~i~\text{ is odd}\}\cup\{1,n\}$ is a feasible solution (assuming $n$ is even): the pair $\{1,n\}$ ensures condition (1), whereas all other pairs ensure condition (2).Remarks(I) Since each pair contains exactly two elements, in order to fulfill condition (2), we need at least $\frac{n}{2}$ pairs. BTW this implies a trivial 2-approximation by returning the whole $S$, since we assume $|S|\leq n$.(II) Another way of looking at the problem is to consider a ladder with $n$ steps (such as the one below), together with a set $S$ of $n$ cycles of the ladder. Each step of the ladder corresponds to some element, and each side edge is an interval $[i,i+1]$. A cycle including steps $s,t$ corresponds exactly to a pair $\{s,t\}$: it covers all consecutive intervals between $s$ and $t$, and it stops at both $s$ and $t$.The question is then whether there is a set $S'\subseteq S$ of $k$ cycles whose union covers all the edges of the ladder (including step edges and side edges).(III) If one was asking only for condition (1), the problem would correspond to the dominating set problem in some interval graph defined from the intervals $[s_i,t_i]$ given by the pairs of $S$ together with additional tiny intervals $[i+\epsilon,i+1-\epsilon]$ for each $i$ in $\{1,\ldots, n-1\}$. This problem is classically solvable in linear time (see e.g. here).Similarly, if one was just asking for condition (2), this could be reduced to the edge cover problem (vertices are the elements, edges are the pairs), which is also polynomial-time solvable by a maximum matching approach.So my question is in the title: Is this problem in P? Is it NP-complete?Any reference to a similar problem is welcome.
What is the complexity of this covering problem?
cc.complexity theory;ds.algorithms;reference request