An independent d-division

Question

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,

Answer 1

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.