From DAGs to levelled DAGs I'm looking into the literature, but I can't find anything interesting, so I thought about asking here for help or for pointers to articles/web pages.
I'm looking for the fastest algorithm that solves the following task:
Given a connected directed acyclic graph $G(V,E)$ with one root $v_0$ as an input, output a levelled DAG $G'(V',E')$, with $V \subset V'$, with the same paths of $G$. So, given $v_i,v_j \in G$, the path $v_i \rightarrow v_j$ is in $G'$, if and only if it is in $G$
In other words, given any vertex $v \in V$, there can be different paths $v_0 \rightarrow v$, and these paths can have different lengths. I need a DAG that has the same vertices (plus additionals) and the same paths as the original one, in a way that every path $v_0 \rightarrow v$ has the same length, for every $v \in V'$.
Is it actually possible? If yes, how can this be achieved?
 A: Begin with a topological sort of $G$, in which we may as well assume the root $v_0$ is the first vertex. (If there are vertices before $v_0$, there is no path from $v_0$ to those vertices anyway, and so we don't need to do anything about them.) Let $v_0, v_1, v_2, \dots, v_n$ be the sequence of vertices we get from the topological sort. With this ordering, all edges $(v_i, v_j)$ in the graph satisfy $i<j$.
Then, we're going to modify the graph to ensure that the path length property holds for $v_1, v_2, v_3, \dots$ in that order. Along the way, we're also going to save that path length: that is, for every $v_i$ we've processed, we've saved a value $\ell_i$ such that all paths $v_0 \to v_i$ have length $\ell_i$ in the modified graph. If there is no path $v_0 \to v_i$, we can set $\ell_i = \infty$. We begin by setting $\ell_0 = 0$.
Suppose that we've processed $v_1, v_2, \dots, v_{k-1}$ and we are now processing $v_k$. Begin by finding the in-neighborhood $N^-(v_k)$ in the original graph $G$: the set $\{v_i \in V(G) : (v_i, v_k) \in E(G)\}$.

*

*Let $\ell_k = 1 + \max\{\ell_i : v_i \in N^-(v_k)\}$. This will be the target path length we shoot for.

*Replace every edge $(v_i, v_k)$ by a path of length $\ell_k - \ell_i$ whose internal vertices are entirely new.

When we're done, it's true that every path $v_0 \to v_k$ in the new graph has length $\ell_k$. On any such path, take the last vertex $v_i \in \{v_0, v_1, \dots, v_{k-1}\}$ preceding $\ell_k$. We must have taken $\ell_i$ steps to get to $v_i$, and then followed the newly added path of length $\ell_k - \ell_i$, so the total length of the path is $\ell_k$.
Also, every newly added vertex $v$ has this property. If $v$ was added when we were building a path $v_i \to v_j$, then every path $v_0 \to v$ is the composition of a path $v_0 \to v_i$, plus the initial segment of the path $v_i \to v_j$ ending at $v$. All paths $v_0 \to v_i$ have the same length, so we conclude all paths $v_0 \to v$ have the same length.
Also, we haven't affected any paths from $v_0$ to previously processed vertices. We have only changed how we get from previous vertices to $v_k$, and there's no way to get back from $v_k$ to any vertices we've seen.
So when we finally process the last vertex $v_n$, the graph will have the desired property for all vertices in $V'$.
