# “Disjunctive” topological sorting

The standard topological sorting has as its input a list of pairs ($x_1$, $y_1$),..., ($x_n$, $y_n$), where ($x_i$, $y_i$) gives the order "$x_i$ precedes $y_i$".

Suppose we replace the 1st component of each pair with a set, i.e. turning ($x_i$, $y_i$) into ($X_i=\{x_{i,1},...,x_{i,n(i)}\}$, $y_i$), which means "at least one element of $X_i$ precedes $y_i$".

Here's the question: is there any efficient algorithm that can find at least one solution for the given input?

Of course we can enumerate over elements of $X_i$ for $i=1,...,n$, and apply the usual algorithm for the standard case. But this means we have to apply the usual algorithm for $|X_1|\times\cdots\times|X_n|$ times. It doesn't seem to be a good idea.

• What algorithm for standard topological sorting do you know? A small modification should suffice. – Adayah Sep 28 '17 at 18:30
• @Adayah I have in mind Kahn's algorithm. But it's not that simple. There might be contradiction; e.g. given $(\{a,b\},c)$, $({c},a)$, the only possible solution is $b>c>a$. In general situations, the contradiction might be harder to detect, because it won't arise until we find the transitive closure. – Pteros Sep 28 '17 at 18:41
• Apply the usual Kahn's algorithm, but instead removing all edges $(u, v)$ (thus decreasing in-degree of $v$) while processing $u$, remove all edges $(U, v)$ such that $u \in U$. Won't that work? – Adayah Sep 28 '17 at 20:13
• @Adayah Oh I think it works. The complexity in this case is still linear (number of edges + number of vertices), right? Please let me know how I should acknowledge you (if I use this result in my project) Thank you! – Pteros Sep 29 '17 at 2:23
• I think the complexity is linear in $\displaystyle |V| + \sum_{(U, v) \in E} |U|$, because on every edge $(U ,v)$ there may be $|U|$ attempts of deletion. This is a simple modification of a classic algorithm, I don't think it needs any acknowledgement, thanks. ;-) – Adayah Sep 29 '17 at 7:21

As @Adayah points out, Kahn's algorithm works as usual, with a minor modification: instead of deleting all edges $(x, y)$ where $x$ has $0$ indegree, delete all edges $(X, y)$ for which $x\in X$.