<p>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.</p>

<p>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 <s>minimizes</s> maximizes $k$.  Add these $2 \epsilon n$ edges to the solution.</p>

<p>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.</p>

<p>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).</p>

<p>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".</p>

<p>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).  </p>

<p>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$.)</p>

CC BY-SA 3.0
2012-06-30T02:48:03.760Z
Nice. and welcome to cstheory !
Suresh Venkat
CC BY-SA 3.0
2012-08-27T09:29:12.940Z
Thanks for your answer, Neal (and sorry, I did not have time to check this earlier)! Even though this does not fully answer my question, it is still a step forward. Just two comments: I think it should be "maximizes k" rather than "minimizes k" (2nd paragraph). Also, to be precise, if one wants a ($1+\epsilon$)-approximation, one should mark every $k=4/\epsilon$'th vertex (since $OPT\geq n/2$ and we then take $2n/k\leq\epsilon OPT$ edges in the first step).
Florent Foucaud
CC BY-SA 3.0
2012-06-30T01:07:24.163Z
2012-08-27T09:53:24.013Z
2012-08-27T09:53:24.013Z
Neal Young
<p><em>Edit: I first misformulated my constraint (2), it is now corrected. I also added more information and examples.</em></p>

<p>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.</p>

<blockquote>
  <p><strong>Instance:</strong> An integer $n$, an integer $k&lt;n$, and a set $S=\{\{s_1,t_1\},\ldots,\{s_n,t_n\}\}$ of $n$ pairs from the set $\{1,\ldots,n\}$.</p>
  
  <p><strong>Question:</strong> Is there a set $S'\subseteq S$ of size $k$ such that for each element $i$ of $\{1,\ldots,n\}$:<br>
  (1) if $i&lt;n$, the interval $[i,i+1]$ is included in some interval $[s_i,t_i]$ defined by a pair in $S'$, and<br>
  <strike>(2) at least one of $i$, $i+1$ belongs to some pair of $S'$?</strike><br>
  (2) $i$ belongs to some pair of $S'$.</p>
</blockquote>

<p><em>Example</em><br>
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).</p>

<p><em>Remarks</em><br>
(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$.</p>

<p>(II) Another way of looking at the problem is to consider a ladder with $n$ steps (such as the one <a href="https://upload.wikimedia.org/wikipedia/commons/c/c1/Ladder_graph_L8.svg" rel="nofollow noreferrer">below</a>), 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$.<br>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).</p>

<p><img src="https://upload.wikimedia.org/wikipedia/commons/c/c1/Ladder_graph_L8.svg"></p>

<p>(III) If one was asking only for condition (1), the problem would correspond to the <a href="http://en.wikipedia.org/wiki/Dominating_set" rel="nofollow noreferrer">dominating set problem</a> 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. <a href="http://www.sciencedirect.com/science/article/pii/0020019088900919" rel="nofollow noreferrer">here</a>).<br>Similarly, if one was just asking for condition (2), this could be reduced to the <a href="http://en.wikipedia.org/wiki/Edge_cover" rel="nofollow noreferrer">edge cover problem</a> (vertices are the elements, edges are the pairs), which is also polynomial-time solvable by a maximum matching approach.</p>

<hr>

<p>So my question is in the title: </p>

<blockquote>
  <p><strong>Is this problem in P? Is it NP-complete?</strong></p>
</blockquote>

<p>Any reference to a similar problem is welcome.</p>

CC BY-SA 3.0
2012-06-01T02:50:39.323Z
It could be somewhere in between… who knows that it cannot be equivalent to, say, graph isomorphism?  :)
Tsuyoshi Ito
CC BY-SA 3.0
2012-06-01T06:52:14.390Z
Sure, that's an option too... But actually I feel this "smells" to be in P - maybe because I hope it to be :)
Florent Foucaud
CC BY-SA 3.0
2012-06-07T07:00:57.057Z
Why does any feasible solution must have a size $\geq \frac{n}{2}$? Could you, please, explain why the set of pairs {$[1, n-1], [2, n]$ } is not feasible.
hbm
CC BY-SA 3.0
2012-06-07T09:45:31.833Z
@hbm: the solution you are proposing does not fulfill condition (2) (even with the constraint of before my update). I have included more explanations now, I hope it's clearer.
Florent Foucaud
CC BY-SA 3.0
2012-06-07T18:26:14.540Z
What about k=n/2? Can we solve the problem for this special case?
domotorp
CC BY-SA 3.0
2012-06-07T18:35:18.620Z
if one enumerates all the cycles is this roughly equivalent to the [set cover problem](http://en.wikipedia.org/wiki/Set_cover_problem) so is the difficulty of applying that algorithm that there are a "large" number of cycles?
vzn
CC BY-SA 3.0
2012-06-18T13:50:35.210Z
@domotorp: I don't know. It might well be possible to characterize these sepcial cases.
Florent Foucaud
CC BY-SA 3.0
2012-06-18T13:52:55.143Z
@vzn: Yes, this is an instance of the set cover problem, but it is well-known that this problem is in general not in P. Applying a "set cover algorithm" (do you mean the greedy approximation algorithm?) as you suggest would not lead to an exact solution.
Florent Foucaud
<cc.complexity-theory><ds.algorithms><reference-request>
What is the complexity of this covering problem?
Florent Foucaud
# What is the complexity of this covering problem?

(Asked by: username_0 on 2012-05-31)

*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
>
> **Question:** Is there a set $S'\subseteq S$ of size $k$ such that for each element $i$ of $\{1,\ldots,n\}$:  
> (1) if $i
> (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](https://upload.wikimedia.org/wikipedia/commons/c/c1/Ladder_graph_L8.svg)), 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).

![](https://upload.wikimedia.org/wikipedia/commons/c/c1/Ladder_graph_L8.svg)

(III) If one was asking only for condition (1), the problem would correspond to the [dominating set problem](http://en.wikipedia.org/wiki/Dominating_set) 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](http://www.sciencedirect.com/science/article/pii/0020019088900919)).  
Similarly, if one was just asking for condition (2), this could be reduced to the [edge cover problem](http://en.wikipedia.org/wiki/Edge_cover) (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.

**Tags:** cc.complexity-theory, ds.algorithms, reference-request

> **Comments:**
> **username_1**: It could be somewhere in between… who knows that it cannot be equivalent to, say, graph isomorphism?  :)  
> **username_0**: Sure, that's an option too... But actually I feel this "smells" to be in P - maybe because I hope it to be :)  
> **username_2**: Why does any feasible solution must have a size $\geq \frac{n}{2}$? Could you, please, explain why the set of pairs {$[1, n-1], [2, n]$ } is not feasible.  
> **username_0**: @username_2: the solution you are proposing does not fulfill condition (2) (even with the constraint of before my update). I have included more explanations now, I hope it's clearer.  
> **username_3**: What about k=n/2? Can we solve the problem for this special case?  
> **username_4**: if one enumerates all the cycles is this roughly equivalent to the [set cover problem](http://en.wikipedia.org/wiki/Set_cover_problem) so is the difficulty of applying that algorithm that there are a "large" number of cycles?  
> **username_0**: @username_3: I don't know. It might well be possible to characterize these sepcial cases.  
> **username_0**: @username_4: Yes, this is an instance of the set cover problem, but it is well-known that this problem is in general not in P. Applying a "set cover algorithm" (do you mean the greedy approximation algorithm?) as you suggest would not lead to an exact solution.  

---

## 1 answers

### Answer by username_5 on 2012-06-30. Score: 8

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

> **Comments:**
> **username_6**: Nice. and welcome to cstheory !  
> **username_0**: Thanks for your answer, Neal (and sorry, I did not have time to check this earlier)! Even though this does not fully answer my question, it is still a step forward. Just two comments: I think it should be "maximizes k" rather than "minimizes k" (2nd paragraph). Also, to be precise, if one wants a ($1+\epsilon$)-approximation, one should mark every $k=4/\epsilon$'th vertex (since $OPT\geq n/2$ and we then take $2n/k\leq\epsilon OPT$ edges in the first step).  

---

