# 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 < 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,

• What have you tried? – 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?$$
• 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. – Tom Jun 20 '20 at 22:04
• 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? – Tom Jun 20 '20 at 22:24