6
$\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$
4
  • 1
    $\begingroup$ cross-posted: stackoverflow.com/questions/63600663/… $\endgroup$
    – user114966
    Aug 26, 2020 at 19:41
  • 2
    $\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$ Aug 26, 2020 at 19:46
  • 1
    $\begingroup$ Since the betweeness problem is NP-hard, this problem is likely to be NP-hard as well. $\endgroup$
    – John L.
    Sep 12, 2021 at 16:33
  • $\begingroup$ "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. $\endgroup$
    – John L.
    May 23, 2022 at 6:11

2 Answers 2

1
$\begingroup$

The decision version of your problem of deciding whether the DAG contains such an order is NP-complete, even if all (X,Y,Z)s are disjoint. It is proven in Appendix B in [1].

[1] Guttmann, W., & Maucher, M. (2006). Constrained ordering.

$\endgroup$
-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$ Aug 26, 2020 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$ Aug 26, 2020 at 21:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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