Ordering of a DAG minimizing some definition of cost

Question

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.

Answer 1

This problem is NP-complete, as the following reduces to it: https://cstheory.stackexchange.com/a/1936/419

The sketch of the reduction is as follows. From a set of tasks $T$ with $n$ tasks and some costs (not to be confused with your cost function!), we will make a DAG that has $N$ indegree 0 vertices (sources), and $N$ outdegree 0 vertices (sinks), where $N$ is some big ($poly(n)$ size) number to be specified later. The DAG will also have an indegree $N$ vertex that has to come right after the sinks, and, similarly, an outdegree $N$ vertex that has to come right before the sources. For each task, we have a vertex that must be between the indegree $N$ vertex and the outdegree $N$ vertex by adding an edges from and to them, respectively. This achieves that the task-vertices are not mixed with the sources and sinks.

Finally, for every task $t$ with a positive cost $c(t)$ we add $nc(t)$ edges from some sources, and for every task $t$ with a negative cost $c(t)$ we add $nc(t)$ edges to some sinks. This achieves that the edges between the tasks won't matter, only the costs will determine the thickness cost that you've defined.

I don't know anything about approximation and heuristics.