Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the cost of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i \mid \exists k>i: (v_j,v_k)\in A\}|$. The problem is: given a DAG, find a topological ordering with minimum cost.
In other words, for each $i$, I consider that a vertex that appeared before $i$ is pending if it still has one or more out-neighbours that did not appear yet, and I want to minimize the maximum number of pending vertices at any time.
It looks like some graph measures (say treewidth, etc.), but I didn't manage to find this in the literature. Has it been studied before?
I'd say it's almost-certainly NP-hard (although I don't have a proof)... would there be any approximation algorithm, or at least some smart heuristic?
Edit: for a little bit of context. This came up while I was trying to program a tool solving a completely unrelated string problem. To make things short: the graph models my input, and I need to compute a set of strings $\mathcal S(v)$ for each node $v$. To compute each $\mathcal S(v)$, I need to know $\mathcal S(u)$ for each node $u$ with an arc $u\rightarrow v$. In the end I'm only interested in $\mathcal S(v)$ for the targets of the graph. Now I want to improve the memory needs: the sets $\mathcal S$ are huge, so I want to keep only a minimum number of them in memory at any time: they correspond to the "pending vertices" defined above.