Topological sort where some nodes can't come in between two other nodes I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come &quot;in between&quot; node X or node Y. In other words, Y &lt; X OR Z &lt; Y.
I've thought about several approaches to this, but can't find a solution. Maybe I can turn every NonBetween relation into &quot;regular edges&quot; and then do a standard topological sort?
Have you heard of any similar problem or solution to this?
EDIT: As pointed out in the comments this doesn't work!
Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $v\rightarrow u$ and $w\rightarrow v$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid topo sort for $G$ respecting NotBetween.
This is clearly $O(V^3)$ because you can implement this with 3 nested loops, then resulting graph has at most $O(V^2)$ edges, and the topological sort of $G'$ will take time $O(V^2)$.
If your relation NotBetween is not a black box and actually has some &quot;known shape&quot; you might be able to skip some triples and do better.