What is the complexity of this covering problem?

Question

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'$.

Example
The 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.

Answer 1

Although this does not resolve the question you raise, some of the previous comments consider approximation algorithms. FWIW, I think a PTAS (poly-time approximation scheme) is possible using dynamic programming. Here's the idea.

Given any instance and $\epsilon > 0$, build a solution as follows. Mark every $(1/\epsilon)$'th vertex. For each marked vertex $i$, from all of the edges $(j,k)$ that "span" $i$ (i.e., that satisfy the constraint (1) for $i$), choose one edge that minimizes $j$ and one that minimizes maximizes $k$. Add these $2 \epsilon n$ edges to the solution.

These edges satisfy the constraints of type (1) for many of the vertices. Meanwhile they contribute $2n\epsilon$ edges to the solution, which is only $O(\epsilon \mbox{OPT})$. To finish, we will find an optimal solution to the remaining problem of finding a set of edges that meets all remaining type (1) and type (2) constraints.

Define a "block" of vertices to be a set of consecutive vertices whose type (1) constraints are met by the edges added so far. Between any two consecutive blocks, there is a sequence of vertices whose type (1) constraints are not met. (Any such sequence has length at most $1/\epsilon$, because the marked vertices have their type (1) constraints met by the edges already added.) Call any such sequence a "neighborhood" of the two adjacent blocks (so each block has a neighborhood to its left and a neighborhood to its right).

Within each neighborhood, for each vertex in the neighborhood, each edge leaving the vertex spans a distance of at most $1/\epsilon$ (because the edge doesn't span any marked vertex). Thus, the vertex has degree at most $1/\epsilon$. Thus, each neighborhood has at most $1/\epsilon$ vertices and touches at most $1/\epsilon^2$ edges. Call any subset of those edges a "configuration" of the neighborhood. If a configuration meets all of the type (1) and type (2) constraints for the vertices in the neighborhood, call the configuration "valid".

For each block $i$, for each pair $(C_i, C_{i+1})$ of valid configurations of the block's two neighborhoods, compute (in polynomial time, using maximum matching etc), the minimum size $F_i(C_i,C_{i+1})$ of any set $S$ of edges (if any exists) such that the edges in $C_i\cup S \cup C_{i+1}$ meet the type (2) constraints for the vertices in the block. Since there are at most $2^{1/\epsilon^2} = O(1)$ configurations, this can be done in polynomial time (for fixed eps).

Now you can solve the original instance by finding a sequence $D_1, D_2, .., D_k$ of valid configurations, one for each neighborhood, that minimizes $\sum_i |D_i| + F_i(D_i, D_{i+1})$, where $F_i$ is as defined in the previous paragraph. This can be done by finding a shortest path in the graph formed by all valid configurations, with an edge of cost $|D_i| + F_i(D_i, D_{i+1})$ from each configuration $D_i$ for neighborhood $i$ to each configuration $D_{i+1}$ for neighborhood $i+1$. (This graph has size $O(2^{1/\epsilon^2} n)$, which is $O(n)$ for fixed $\epsilon$.)