# How efficiently can one find small subcovers for integer intervals?

This question is inspired by one of my professors giving out
sequential lecture notes that have a significant amount of overlap :-).

What is known about the following problems?

Given a set of integer intervals whose union is an integer interval, find a subset
with the same union that minimizes the number of intervals in the subset.

Given a set of integer intervals whose union is an integer interval, find a subset with the
same union that minimizes the sum of the cardinalities of the intervals in the subset.

• "with the same union" means "the union of the subset is equal to the union of the original set". $\hspace{.39 in}$ – user6973 Oct 18 '13 at 20:49
• The first problem is an instance of the Min Set Cover problem with a set system of VC dimension 2, and admits a constant factor approximation, for example using citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.8834. But that seems like an overkill, maybe you can do better in this 1-dimensional case – Sasho Nikolov Oct 19 '13 at 17:09

Let me restate the first problem:

Problem: Given a set of intervals $\mathcal{S} = \{ I_1, I_2,\ldots,I_n\}$, minimize $|\mathcal{C}|$, where $\mathcal{C} =\{ I_{j_1}, I_{j_2},\ldots,I_{j_k}\} \subseteq\mathcal{S}$ and $\bigcup_{l=1}^{n}I_l = \bigcup_{m=1}^{k}I_{j_m}$

Define: Graph $G(V,E)$, $V = \{v_1, v_2, \ldots, v_n ,s ,t \}$ where,

1. Vertex $v_j \in V$ denotes interval $I_j$.
2. Vertices $v_k, v_l$ have an edge between them if their corresponding intervals $I_k,\; I_l$ overlap.
3. Source vertex $s$ and $v_j$ have an edge between them if $v_j$'s corresponding interval $I_j$ contains the leftmost point of $\bigcup_{l=1}^{n}I_l$.
4. Similarly sink vertex $t$ and $v_j$ have an edge between them if $v_j$'s corresponding interval $I_j$ contains the rightmost point of $\bigcup_{l=1}^{n}I_l$.

Answer: The intervals corresponding to the vertices in the 'shortest vertex path' between $s$ and $t$ gives the minimum set cover!

If I have understood your 2nd question correctly, it is nothing but the weighted 1-dimensional set cover problem.

Remark 1: The intervals $I_j$ considered above might possibly have non-integer end-points.

Remark 2: One can solve this problem using dynamic programming, which I think has "lower" complexity than the shortest path solution.

EDIT-1: For the ease of exposition, I have considered only closed intervals in the above problem.

• "... for a rigorous proof" of the correspondence you refer to, or of something else? $\hspace{.99 in}$ – user6973 Oct 22 '13 at 22:02
• A small detail: I think you have to treat the intervals $[0,2)$ and $[2,5]$ as overlapping (i.e., the condition is that their union must itself form a new interval that is larger than either of the two component intervals). – D.W. Oct 23 '13 at 0:28
• @D.W. Yes. You are correct. – Vivek Bagaria Oct 23 '13 at 4:07
• For a rigorous proof of the above solution, refer section 4.3.1 from arxiv.org/abs/1307.5230v1. – Vivek Bagaria Oct 23 '13 at 4:11