3
$\begingroup$

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?
$\endgroup$
7
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.