3
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ cross-posted: stackoverflow.com/questions/63600663/… $\endgroup$ – Dmitry Aug 26 '20 at 19:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Bernardo Subercaseaux Aug 26 '20 at 19:46
-1
$\begingroup$

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 "known shape" you might be able to skip some triples and do better.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ – Bernardo Subercaseaux Aug 26 '20 at 20:49
  • $\begingroup$ Hmm, nice catch. It still feels though like it should not need much more work than than just generating a modified graph and running a topo sort on it... $\endgroup$ – elbrunovsky Aug 26 '20 at 21:00

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.