<p>This problem is NP-complete, as the following reduces to it:
<a href="https://cstheory.stackexchange.com/a/1936/419">https://cstheory.stackexchange.com/a/1936/419</a></p>

<p>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.</p>

<p>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.</p>

<p>I don't know anything about approximation and heuristics.</p>

CC BY-SA 3.0
2016-07-26T11:06:51.047Z
Thanks, nice reduction. This confirms my intuition about hardness... but I'm still looking for any positive way to approach it
tarulen
CC BY-SA 3.0
2016-07-23T18:24:06.670Z
2016-07-23T18:24:06.670Z
2017-04-13T12:32:28.167Z
domotorp
<p>Consider a DAG $(V,A)$ with a topological ordering $(v_1,v_2,\ldots,v_n)$. I define the <em>cost</em> of this ordering as the maximum over all $1\leq i\leq n$ of $|\{j\leq i
\mid \exists k&gt;i: (v_j,v_k)\in A\}|$. 
The problem is: <strong>given a DAG, find a topological ordering with minimum cost</strong>.</p>

<p>In other words, for each $i$, I consider that a vertex that appeared before $i$ is <em>pending</em> 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.</p>

<p>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? </p>

<p>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?</p>

<p><strong>Edit</strong>: 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. </p>

CC BY-SA 3.0
2016-07-22T17:06:17.880Z
What's the context in which you ran across this?  Is there a motivation or practical application?
D.W.
CC BY-SA 3.0
2016-07-26T11:04:17.390Z
@DW somehow, yes... see edit
tarulen
CC BY-SA 3.0
2016-07-26T13:24:57.513Z
https://en.wikipedia.org/wiki/Pebble_game
domotorp
CC BY-SA 3.0
2016-07-31T02:34:51.257Z
You may want to look at linear ordering problems. See the paper below and some refs in that paper. http://epubs.siam.org/doi/abs/10.1137/S0097539702413197
Chandra Chekuri
<graph-theory><approximation-algorithms><directed-acyclic-graph><topological-sorting>
Ordering of a DAG minimizing some definition of cost
tarulen
# Ordering of a DAG minimizing some definition of cost

(Asked by: username_0 on 2016-07-21)

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.

**Tags:** graph-theory, approximation-algorithms, directed-acyclic-graph, topological-sorting

> **Comments:**
> **username_1**: What's the context in which you ran across this?  Is there a motivation or practical application?  
> **username_0**: @DW somehow, yes... see edit  
> **username_2**: https://en.wikipedia.org/wiki/Pebble_game  
> **username_3**: You may want to look at linear ordering problems. See the paper below and some refs in that paper. http://epubs.siam.org/doi/abs/10.1137/S0097539702413197  

---

## 1 answers

### Answer by username_2 on 2016-07-23. Score: 4

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.

> **Comments:**
> **username_0**: Thanks, nice reduction. This confirms my intuition about hardness... but I'm still looking for any positive way to approach it  

---

