<p>Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.<br>
It is NP-complete:  </p>

<blockquote>
  <p>M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:<br>
  "Complexity Results for Bandwidth Minimization"<br>
  SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495 </p>
</blockquote>

<p>It is problem [GT41] in the NP-completeness book by Garey and Johnson.</p>

<p>The special case where every vertex in $G=(V,E)$ has indegree $\Theta(|V|)$ has a polynomial time approximation algorithm with worst case guarentee 2:<br>
<a href="https://www.nada.kth.se/~viggo/wwwcompendium/node54.html" rel="nofollow noreferrer">https://www.nada.kth.se/~viggo/wwwcompendium/node54.html</a></p>

CC BY-SA 4.0
2018-05-25T00:49:53.427Z
The 2-approximation is for a very restricted class of graphs. I am not sure what is known in general. Bandwidth in undirected graphs admits a poly-logarithmic approximation. https://www.sciencedirect.com/science/article/pii/S0022000099916823
Chandra Chekuri
CC BY-SA 4.0
2018-05-24T08:36:27.757Z
2018-05-25T08:08:10.983Z
2018-05-25T08:08:10.983Z
Gamow
<p>Motivation: I want to compute a topological sort order in which the connected vertices are close to each other. </p>

<p>Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort with minimum <em>maximum edge length (MEL)</em>, where <em>MEL</em> in a valid topological sort order $v_1, v_2 \ldots v_n$ is defined as $\max_{(v_i, v_j) \in E} \ |j - i|$.</p>

<graph-algorithms><sorting><directed-acyclic-graph><partial-order><topological-sorting>
Computing topological sort while keeping edges "short"
Chirag Jain
# Computing topological sort while keeping edges "short"

(Asked by: username_0 on 2018-05-24)

Motivation: I want to compute a topological sort order in which the connected vertices are close to each other.

Problem statement: Given a DAG $G(V,E)$ with $n$ vertices, compute a topological sort with minimum *maximum edge length (MEL)*, where *MEL* in a valid topological sort order $v\_1, v\_2 \ldots v\_n$ is defined as $\max\_{(v\_i, v\_j) \in E} \ |j - i|$.

**Tags:** graph-algorithms, sorting, directed-acyclic-graph, partial-order, topological-sorting


---

## 1 answers

### Answer by username_1 on 2018-05-24. Score: 9 | Accepted answer

Your problem is known under the name MINIMUM DIRECTED BANDWIDTH.  
It is NP-complete:

> M.R. Garey, R.L. Graham, D.S. Johnson and D.E. Knuth:  
> "Complexity Results for Bandwidth Minimization"  
> SIAM Journal on Applied Mathematics 34, (1978), pp. 477-495

It is problem [GT41] in the NP-completeness book by Garey and Johnson.

The special case where every vertex in $G=(V,E)$ has indegree $\Theta(|V|)$ has a polynomial time approximation algorithm with worst case guarentee 2:  
<https://www.nada.kth.se/~viggo/wwwcompendium/node54.html>

> **Comments:**
> **username_2**: The 2-approximation is for a very restricted class of graphs. I am not sure what is known in general. Bandwidth in undirected graphs admits a poly-logarithmic approximation. https://www.sciencedirect.com/science/article/pii/S0022000099916823  

---

