<p>The problem is $\mathsf{NP}$-hard. See [GT41] DIRECTED BANDWIDTH in Garey and Johnson.</p>

CC BY-SA 3.0
2013-12-10T16:25:55.597Z
2013-12-10T16:25:55.597Z
Kristoffer Arnsfelt Hansen
<p>A topological sort of a graph $G(V,E)$ consisting of $n$ vertices assigns a label $L(v_x)$ to a vertex $v_x$ where $L$ is defined as $L:V \rightarrow \{1,\dots,n\}$. </p>

<p>Let additional constraints over the labels that the topological sort will assign to be defined as follows.  For every vertex pair $(v_x,v_y)$ let $d(v_x,v_y)$ be the permitted difference between $L(v_x)$ and $L(v_y)$ i.e. $L(v_x) - L(v_y) \leq d(v_x,v_y)$. $d$ is defined as $d:V \times V \rightarrow \{0,\dots,n-1\}$. A solution to this variant of Constrained Topological Sort (CTS) will compute a tolopological sort satisfying the difference constraints for all possible pairs of vertices in $G$.</p>

<ul>
<li>Is a linear time solution to CTS possible?   </li>
<li>Is there an existing work where I can refer to?</li>
</ul>

<graph-algorithms><topological-graph-theory>
Topological sort with constraints on the relative difference between the vertex labels
Umar
# Topological sort with constraints on the relative difference between the vertex labels

(Asked by: username_0 on 2013-12-10)

A topological sort of a graph $G(V,E)$ consisting of $n$ vertices assigns a label $L(v\_x)$ to a vertex $v\_x$ where $L$ is defined as $L:V \rightarrow \{1,\dots,n\}$.

Let additional constraints over the labels that the topological sort will assign to be defined as follows. For every vertex pair $(v\_x,v\_y)$ let $d(v\_x,v\_y)$ be the permitted difference between $L(v\_x)$ and $L(v\_y)$ i.e. $L(v\_x) - L(v\_y) \leq d(v\_x,v\_y)$. $d$ is defined as $d:V \times V \rightarrow \{0,\dots,n-1\}$. A solution to this variant of Constrained Topological Sort (CTS) will compute a tolopological sort satisfying the difference constraints for all possible pairs of vertices in $G$.

* Is a linear time solution to CTS possible?
* Is there an existing work where I can refer to?

**Tags:** graph-algorithms, topological-graph-theory

---

## 1 answers

### Answer by username_1 on 2013-12-10. Score: 7 | Accepted answer

The problem is $\mathsf{NP}$-hard. See [GT41] DIRECTED BANDWIDTH in Garey and Johnson.


---

