Testing/Identifying a Topological Sorting 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?
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.