What is the complexity of this covering problem?
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 &gt; 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$.)