[Solved]: Relation between the "Point-Cover-Interval" problem and the "Interval Scheduling" problem

Problem Detail: 

Point-Cover-Interval Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a minimum number of points $P$ such that each interval contains some point, that is $\forall I \in \mathcal{I}: \exists p \in P, p \in I$.

Interval Scheduling Problem: Given a set $\mathcal{I}$ of $n$ intervals $[s_1, f_1], \ldots, [s_n, f_n]$ along a real line, find a maximum number of intervals such that no two of them overlap.

Interestingly, the two problems above have exactly the same greedy algorithm, illustrated by the following figure (from [1]; for the interval scheduling problem; see the "Greedy Algorithm" part below).

Since they share the same algorithm, I expect that they are the same (or, at least closely related) problem, say, in the view of reduction. However, I failed to reduce them to each other.

Question: Are these two problems the same? Or what is the relation between them? Can we reduce them to each other?

Note that the first problem asks for a minimum solution while the second one for a maximum solution.

---

Greedy Algorithm: The greedy algorithm for the "Interval Scheduling" problem is as follows:

• sort the intervals in increasing order of their finishing times, still denoted as $\mathcal{I}$.
• while ($\mathcal{I} \neq \emptyset$) choose the first $I \in \mathcal{I}$, do:
  • add $I$ into the result-set; (darker lines in the figure)
  • delete all intervals from $\mathcal{I}$ that conflicts with $I$ (dashed lines in the figure).

For the "Point-Cover-Interval" problem, we simply collect the finishing time point of each interval $I$ chosen in each iteration in the algorithm above.

[1]: Algorithm Design. By Jon Kleinberg and Éva Tardos. (Section 4.1)

Asked By : hengxin

Answered By : Aryabhata

Here is a proof that the two numbers are equal:

For every interval $I$ consider the largest set of disjoint intervals with $I$ as the rightmost interval. This has a size, say $D_I$.

Now if $D_I = D_J$, then $I$ and $J$ have to intersect, so the set of intervals with equal $D_I$ values all pairwise intersect each other, and so have a common point (by the 1D version of Helly's theorem, or by just considering the intervals arranged in order of their left endpoints).

Now if $d = \max D_I$ (the size of the largest set of non-intersecting intervals), then we have $D_I$ taking all the values $\{1, 2, \dots, d\}$, and thus $d$ points are enough to cover all the intervals, and we need at least $d$ to cover the largest set of disjoint intervals.

For some related reading, look at Mirsky's theorem, which is a dual of Dilworth's theorem.

Dilworth's theorem says that in a set of elements with a partial order defined on them, the size of the largest antichain (antichain is a set of elements not comparable to each other) is same as the size of the smallest partition into chains (each set of the partition is a total ordered set).

Mirsky's theorem says that the size of the largest chain is the same as the smallest number of antichains into which the set might be partitioned.

In this case defines your order relation as follows:

$$I = (i,j) \lt I' = (i', j') \iff j \lt i'$$

Basically, two disjoint intervals are comparable, with the left one being smaller.

Because of Helly's theorem, the two numbers you are computing are exactly the numbers in Mirsky's theorem, which is defined as the height of the the partial order (Dilworth's theorem defines the width).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43197