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/…
– user114966
Aug 26, 2020 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. Aug 26, 2020 at 19:46
• Since the betweeness problem is NP-hard, this problem is likely to be NP-hard as well. Sep 12, 2021 at 16:33
• "the node Y cant come 'in between' node X and node Z. In other words, Y < X OR Z < Y." Shouldn't it be "In other words, neither X< Y < Z nor Z < Y < Z is true"? The case of concern is Z < Y < X. May 23, 2022 at 6:11

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. Aug 26, 2020 at 20:49