# 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 "in between" node X or node Y. In other words, Y < X OR Z < Y.

I've thought about several approaches to this, but can't find a solution. Maybe I can turn every NonBetween relation into "regular edges" and then do a standard topological sort?

Have you heard of any similar problem or solution to this?

• cross-posted: stackoverflow.com/questions/63600663/… – Dmitry Aug 26 '20 at 19:41
• I think it's interesting to start by the case in which you don't have any initial edges, only the relation NotBetween. It might be that this already hard. Your problem is clearly in NP, but I don't see a polynomial algorithm at first glance. – Bernardo Subercaseaux Aug 26 '20 at 19:46

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)$$.
• I don't think this works. Imagine nodes are numbers 1,2,3, and you have no original edges but only restrictions NotBetween(1,2,3) and NotBetween(3,1,2). Then in your approach the resulting graph has a cycle $1 \to 2 \to 3 \to 1$. And yet $3,2,1$ is a valid sort. Perhaps you meant to add edges $v \to u$ and $w \to v$? But this would also fail, as your adding both edges, when the restriction is an or. – Bernardo Subercaseaux Aug 26 '20 at 20:49