0
$\begingroup$

This was from a test from my university:

Consider $T = t_1, t_2, \cdots, t_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum number of intervals such that their "union" intersects all other intervals. The question then asked for an optimal greedy algorithm.

From what I can see, this is a vertex cover problem (each interval is a vertex; draw an edge between each pair of intervals that intersect), which is NP-complete on general graphs.

Consider $W(i)$ the number of intervals intersecting $i$, and $M$ a set of intervals already covered. Here is my solution:

  1. Order $T$ by $W$ and insert in $T_{ord}$;
  2. If $T_{ord} = \emptyset$ terminate
  3. Remove the first element $e$ from $T_{ord}$;
  4. If $e \in M$ go to $2$;
  5. Decrease $1$ for every element $e^{'}$that intersect $e$, and $M \cup\{e,e^{'}\}$;
  6. Order $T_{ord}$ and go to $2$.

I managed come up with a greedy solution, but couldn't come up with a counterexample. Given that, I was thinking if this is a special case of the vertex cover problem. Is it?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ @DavidRicherby: That's the answer I imagined s/he would give; notice that my example instance shows that the original problem does not correspond to finding a vertex cover in this graph. (Specifically: Consider the graph formed by the intervals {[1, 3], [2, 4], [1, 4]}: since [1, 3] and [2, 4] overlap, there is an edge in the corresponding graph, so at least one of its endpoints must be included in the solution -- but of course neither interval is needed for the original problem, which has {[1, 4]} as its unique optimal solution.) $\endgroup$
    – j_random_hacker
    May 31, 2017 at 12:17
  • 2
    $\begingroup$ A special case can be easier than the general case. $\endgroup$
    – Yuval Filmus
    May 31, 2017 at 14:04
  • 1
    $\begingroup$ We get asked this kind of question a lot, so we've written some general reference material on the subject: cs.stackexchange.com/q/59964/755. I suggest you try applying the methods described there, and then come back and edit the question to show how far you've gotten by trying those techniques, what progress you've made, and what stage you're stuck at. Have you tried random testing on a million small random examples? That's simple, easy to implement, and often very effective. $\endgroup$
    – D.W. ♦
    May 31, 2017 at 19:40
  • $\begingroup$ I wonder why someone deleted my comment hinting that this is not a special case of vertex cover... Not clear enough? $\endgroup$
    – j_random_hacker
    May 31, 2017 at 21:28

1 Answer 1

Reset to default
1
$\begingroup$

This is dominating set, not vertex cover.

The graph has the set of intervals as vertices and two vertices are adjacent if the corresponding intervals overlap. Such a graph is known as an interval graph, which is a special case of intersection graphs (vertices are sets of some kind, and two vertices are adjacent if their sets intersect).

You're looking for a minimum-sized set $S$ of intervals such that every other interval intersects at least one interval in $S$. In the interval graph, this means that you're looking for a minimum-sized set $S$ of vertices such that every other vertex is adjacent to $S$: this is a dominating set.

The problems of omputing minimum vertex covers and minimum dominating sets are both NP-hard on general graphs. However, on interval graphs, both problems can be solved in polynomial time, by

  • M.V. Marathe, R. Ravi and C. Pandu Rangan, Generalized vertex covering in interval graphs. Discrete Applied Mathematics, 39(1):87–93, 1992.
  • K.S. Booth and J.H. Johnson, Dominating sets in chordal graphs. SIAM Journal on Computing, 11(1), 191–199, 1982.

In the former case, a $2$-vertex cover is an ordinary vertex cover; in the latter, the algorithm actually works for all for all directed-path graphs, and every interval graph is a directed-path graph.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Wow, thanks! I also appreciate the papers (I tried to find something about this, but I guess I didn't get the terminology right). $\endgroup$
    – yZaph
    Jun 1, 2017 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.