You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the best algorithm that could identify the graphs among $G_1, G_2, ..., G_n$ that have $(v_1,v_2,...,v_m)$ as a topological sort? Could someone test whether $(v_1,v_2,...,v_m)$ is a topological sort of a DAG $G$ over $V$ in sub-linear time?

  • 6
    $\begingroup$ Are you able to build a data structure based on the set of graphs before being presented with the ordering of the vertices? You need to look at all $n$ graphs and all $m-1$ edges in the ordering, so unless you're allowed to preprocess the graphs somehow, it doesn't seem like you could beat linear time. $\endgroup$ – mjqxxxx Jan 20 '11 at 5:29
  • $\begingroup$ Hsien-Chih Chang, what would be a good pre-processing technique that can allow a better solution? Some type of hashing? I guess you can beat linear time if can approximate the solution (probabilistic algorithm). $\endgroup$ – user2471 Jan 21 '11 at 0:37
  • $\begingroup$ @user2471: As I said in your previous answer, this post is written by @Steve, not me ;) $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 21 '11 at 1:00
  • $\begingroup$ Sorry Hsien-Chih Chang, my question was meant for everyone :) $\endgroup$ – user2471 Jan 21 '11 at 2:04
  • $\begingroup$ @user2471, no need to apologize! Hope someone who is familiar to this question will post a nice answer :D $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 21 '11 at 5:28

This can be done in nearly linear time.

Let the permutation be $\pi = (v_1,\dots,v_m)$, and let $k = k(\pi)$ be the number of steps needed to check a single edge $(u,v)$ against $\pi$. It is then enough to check that each of the $M_i$ edges of $G_i$ is compatible with $\pi$, which can be done in $O(kM_i)$ time, or $O(k\sum M_i)$ overall.

By preprocessing $\pi$ one can reduce $k$ down to two lookups in an array containing $m$ entries each of $\log\, m$ size, and a comparison between two $(\log\ m)$-bit entries in the array; the array element $a[w]$ contains the index of $w$ in $\pi$ considered as an ordered list. This means that $k = O(\log\, m)$ yielding $O((\log\, m)\sum M_i)$ time overall for the upper bound.

As @mjqxxxx points out, every edge of every graph may be relevant. This creates a lower bound of $\Omega(K\sum M_i)$ steps, where $K$ is the least amount of work that needs to be done for every graph edge; it is possible that some approaches can amortize the cost so that $K = o(\log\, m)$. This is still going to be $\Omega(\sum M_i)$ at best, so there is not much of a gap left.

| cite | improve this answer | |
  • $\begingroup$ What algorithm can be used to make k = log m. Is it suffix trees? $\endgroup$ – vincent mathew Mar 30 '15 at 11:03

Trivial Method:

GS = {G1,G2...G3}
for v in (v1,v2,...vm)
      remove all graphs from GS where indegree(v) != 0
      remove v and attached edges from remaining GS

It is not as fast as you want. But it solves one problem that "there can be multiple valid topological orderings of DAG". And finding them all is not a good idea.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy