An independent d-division 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 &lt; 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 &lt; i_2 &lt; \dots &lt; i_{d-1} &lt; 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 &lt; d$ and forall $i_r &lt; j_1 &lt; 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 &quot;continuous&quot;. 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,
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.