Topological sort with constraints on the relative difference between the vertex labels 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?
The problem is $\mathsf{NP}$-hard. See [GT41] DIRECTED BANDWIDTH in Garey and Johnson.