3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "with the same union" means "the union of the subset is equal to the union of the original set". $\hspace{.39 in}$ $\endgroup$ – user6973 Oct 18 '13 at 20:49
  • 1
    $\begingroup$ 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 $\endgroup$ – Sasho Nikolov Oct 19 '13 at 17:09
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "... for a rigorous proof" of the correspondence you refer to, or of something else? $\hspace{.99 in}$ $\endgroup$ – user6973 Oct 22 '13 at 22:02
  • $\begingroup$ 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). $\endgroup$ – D.W. Oct 23 '13 at 0:28
  • $\begingroup$ @D.W. Yes. You are correct. $\endgroup$ – Vivek Bagaria Oct 23 '13 at 4:07
  • 1
    $\begingroup$ For a rigorous proof of the above solution, refer section 4.3.1 from arxiv.org/abs/1307.5230v1. $\endgroup$ – Vivek Bagaria Oct 23 '13 at 4:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy