# Ordering of a DAG minimizing some definition of cost

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.

• What's the context in which you ran across this? Is there a motivation or practical application?
– D.W.
Jul 22 '16 at 17:06
• @DW somehow, yes... see edit Jul 26 '16 at 11:04
• en.wikipedia.org/wiki/Pebble_game Jul 26 '16 at 13:24
• Your underlying graph problem is very close to One-Shot Black Pebbling, which I wouldn't have remembered if domotorp hadn't mentioned pebbling games. ​ The main or only part of reducing your underlying graph problem to that is removing vertices from which no targets are reachable, and then attaching [an outward edge to a new sink vertex] to each target. ​ If you need to hold S of the targets in memory the whole time (rather than processing them as you get them), then finally add a new vertex with an edge from each former-sink. ​ ​ ​ ​ ​ ​ ​ ​
– user6973
Jul 26 '16 at 13:53
• Also, have you tried approximating the treewidth of the induced undirected graph? ​ This seems like the sort of problem that might be FPT when parameterized by pathwidth, or even treewidth. ​ ​ ​ ​
– user6973
Jul 26 '16 at 14:09

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.