I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms):

Let $G = (V,E)$ an undirected graph whose vertices $V = \{v_1,\dots,v_n\}$ appear in this order on the real line (meaning forall $1 \leq i < j \leq n$, $v_i$ appears before $v_j$).

A $d$-divison of $G$'s vertices is a division into $d$ different intervals, meaning the choice of $d-1$ indices $1 \leq i_1 < i_2 < \dots < i_{d-1} < n$ which define the intervals: $$ [v_1,\dots,v_{i_1}], [v_{i_1+1},\dots,v_{i_2}],\dots,[v_{i_{d-1}+1},\dots,v_n]. $$

A $d$-division is called independent if there are no two neighboring vertices in the same interval. Meaning, the division is independent if forall $0 \leq r < d$ and forall $i_r < j_1 < j_2 \leq i_{r+1}$ we have $\{v_{j_1},v_{j_2}\} \notin E$, where $i_0 = 0$ and $i_d = n$.

Offer an algorithm with time complexity $O(V+E)$ that finds an independent $d$-division of $G$ such that $d$ is minimal. Prove the correctness of the algorithm.

Notice: The division in this exercise is "continuous". For instance, if $v_1$ and $v_3$ are on the same interval, then $v_2$ is on the same interval with them. Also, there are no edges between any two vertices in the same interval. For instance, if the first interval in the division is $[v_1,v_2,v_3]$, then $\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_1\} \notin E$.

Thanks a lot,

  • $\begingroup$ What have you tried? $\endgroup$ – nir shahar Jun 20 '20 at 21:49

Think about what happens when you manage to find the first interval, say it is $[v_1,...,v_k]$ for some $k$. Then what would you be able to say about the minimal division of $v_{k+1},...,v_n?$

Think also about how you could find the first interval. Starting from an empty interval and expanding it (how?) should do the trick.

  • $\begingroup$ Hi, thanks for your help. My idea is to iterate all the vertices starting from $v_1$ and on. I try to add as much vertices to its interval as possible, by checking neighbors: if a vertex $u$ is not a neighbor of any vertex in the interval, I add it. When there are no more vertices which can be added to a certain interval, I move to the next interval, and do so until I finish the iteration. Intuitively, I think it will work (but please correct me if I'm wrong), but I need some direction for the correctness proof, if possible. $\endgroup$ – Tom Jun 20 '20 at 22:04
  • $\begingroup$ This will work. For the correctness proof, try to show in induction that the algorithm works. A useful lemma for this would be that the algorithm outputs the biggest possible interval as the first interval $\endgroup$ – nir shahar Jun 20 '20 at 22:11
  • $\begingroup$ I think that given your last comment, I have a proof scheme now: First, prove the lemma. Then, show in induction on $d$ that the algorithm outputs a correct division of $V$. Am I right? $\endgroup$ – Tom Jun 20 '20 at 22:24
  • $\begingroup$ Yes that is correct. But you will need to think on how to prove the induction (the lemma is easier to prove) from the lemma. $\endgroup$ – nir shahar Jun 20 '20 at 22:45

Your Answer

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

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