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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ cross-posted: stackoverflow.com/questions/63600663/… $\endgroup$
    – user114966
    Commented 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$
    – Bernardo Subercaseaux
    Commented 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.
    Commented 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.
    Commented May 23, 2022 at 6:11

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\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
    Commented 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$
    – elbrunovsky
    Commented 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.