<p>Every instance of Q can be transformed into an instance of the Multiple Set Cover Problem, where the locations are the intervals $[l_i,r_i]$, covering a consecutive sequence of demand points (=integers $d_i$).</p>

CC BY-SA 3.0
2014-05-07T09:51:17.677Z
Can you improve the answer adding the definition of Multiple Set Cover Problem (MSCP) and more details about the reduction ? In particular, an instance of MSCP (at least the "version" I know) is a bipartite graph $G = (V_1,V_2,E)$ and only $V_1$ is a union of disjoint sets; in which way the reduction maps the edges from $V_1$ to $V_2$?
Marzio De Biasi
CC BY-SA 4.0
2020-04-27T20:19:05.560Z
I don't understand the point of this answer. Reducing the given problem _to_ an NP-hard problem doesn't show the given problem is hard.  (Nor does it show the given problem is in P, of course.)
Neal Young
CC BY-SA 3.0
2014-02-05T09:26:35.037Z
2014-02-05T09:26:35.037Z
Benjamin
<p>Consider the following <strong>problem $Q$</strong>: We are given an integer $n$, and $k$ intervals $[l_i,r_i]$ with $1\leq l_i\leq r_i\leq 2n$. We are also given $2n$ integers $d_1,…,d_{2n}\geq 0$. The task is to select a minimum number of intervals $[l_i,r_i]$ such that for every $i=1,…,2n$, at least $d_i$ intervals containing the integer $i$ are selected.</p>

<p>It is not hard to see that $Q$ can be solved in polynomial time (see below).</p>

<p>Now consider the following slightly modified <strong>problem $Q’$</strong>: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d_{2i-1}$ intervals containing the integer $2i-1$ or at least $d_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).</p>

<p><strong>My question: Can $Q’$ be solved in polynomial time?</strong></p>

<p>Here are two ways to solve $Q$ efficiently:</p>

<p>A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.</p>

<p>An integer program: For each interval $[l_i,r_i]$ introduce a decision variable $x_i\in\{0,1\}$ with $x_i=1$ iff the interval is selected. The objective is to minimize $ x_1+…+x_k$, subject to the constraints $\sum_{j:i\in[l_j,r_j]} x_j\geq d_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.</p>

<p>Thanks for any hints, and also for references!</p>

CC BY-SA 4.0
2021-05-19T15:33:11.130Z
You may be able to adapt the NP-hardness proof from [Chrobak, M., Woeginger, G.J., Makino, K. et al. Caching Is Hard—Even in the Fault Model. Algorithmica 63, 781–794 (2012)](https://doi.org/10.1007/s00453-011-9502-9).
Neal Young
<cc.complexity-theory><np-hardness>
Complexity of interval cover problem
Torsten Mütze
# Complexity of interval cover problem

(Asked by: username_0 on 2013-05-06)

Consider the following **problem $Q$**: We are given an integer $n$, and $k$ intervals $[l\_i,r\_i]$ with $1\leq l\_i\leq r\_i\leq 2n$. We are also given $2n$ integers $d\_1,…,d\_{2n}\geq 0$. The task is to select a minimum number of intervals $[l\_i,r\_i]$ such that for every $i=1,…,2n$, at least $d\_i$ intervals containing the integer $i$ are selected.

It is not hard to see that $Q$ can be solved in polynomial time (see below).

Now consider the following slightly modified **problem $Q’$**: The input of the problem is the same as before. However, the task now is to select a minimum number of intervals such that for every $i=1,…,n$, at least $d\_{2i-1}$ intervals containing the integer $2i-1$ or at least $d\_{2i}$ intervals containing the integer $2i$ are selected (with “or” we mean the usual logical or).

**My question: Can $Q’$ be solved in polynomial time?**

Here are two ways to solve $Q$ efficiently:

A simple greedy algorithm: Sweep through the intervals from left-to-right and select only as few intervals as are necessary to “satisfy” the numbers $d\_i$. Whenever there is a choice between different intervals, choose the one(s) with maximal right endpoint.

An integer program: For each interval $[l\_i,r\_i]$ introduce a decision variable $x\_i\in\{0,1\}$ with $x\_i=1$ iff the interval is selected. The objective is to minimize $ x\_1+…+x\_k$, subject to the constraints $\sum\_{j:i\in[l\_j,r\_j]} x\_j\geq d\_i$. The constraint matrix of this integer program has the consecutive ones property and therefore the linear programming relaxation of this program has an integer optimal solution.

Thanks for any hints, and also for references!

**Tags:** cc.complexity-theory, np-hardness

> **Comments:**
> **username_1**: You may be able to adapt the NP-hardness proof from [Chrobak, M., Woeginger, G.J., Makino, K. et al. Caching Is Hard—Even in the Fault Model. Algorithmica 63, 781–794 (2012)](https://doi.org/10.1007/s00453-011-9502-9).  

---

## 1 answers

### Answer by username_2 on 2014-02-05. Score: -2

Every instance of Q can be transformed into an instance of the Multiple Set Cover Problem, where the locations are the intervals $[l\_i,r\_i]$, covering a consecutive sequence of demand points (=integers $d\_i$).

> **Comments:**
> **username_3**: Can you improve the answer adding the definition of Multiple Set Cover Problem (MSCP) and more details about the reduction ? In particular, an instance of MSCP (at least the "version" I know) is a bipartite graph $G = (V_1,V_2,E)$ and only $V_1$ is a union of disjoint sets; in which way the reduction maps the edges from $V_1$ to $V_2$?  
> **username_1**: I don't understand the point of this answer. Reducing the given problem _to_ an NP-hard problem doesn't show the given problem is hard.  (Nor does it show the given problem is in P, of course.)  

---

