1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What algorithm for standard topological sorting do you know? A small modification should suffice. $\endgroup$ – Adayah Sep 28 '17 at 18:30
  • $\begingroup$ @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. $\endgroup$ – Pteros Sep 28 '17 at 18:41
  • $\begingroup$ 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? $\endgroup$ – Adayah Sep 28 '17 at 20:13
  • $\begingroup$ @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! $\endgroup$ – Pteros Sep 29 '17 at 2:23
  • $\begingroup$ 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. ;-) $\endgroup$ – Adayah Sep 29 '17 at 7:21
2
$\begingroup$

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$.

$\endgroup$

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.