Testing if a given DAG is a lattice
The DAG represents the covering relation $\lessdot$ of a partial order $&lt;$, also known as its Hasse diagram. An element $y$ covers an element $x$, in symbols $x \lessdot y$, if $x &lt; y$ and no $z$ satisfies $x &lt; z &lt; y$.

Suppose that $Y$ is a non-empty set of elements in the partial order which is upwards closed (if $z \in Y$ and $u &gt; z$ then $u \in Y$), and in which any two elements have a join. Let $y \notin Y$ be such that $Y \cup \{y\}$ is also upwards closed. Then for all $z \in Y$,
$$
z \lor y = \min_{y \lessdot u} z \lor u,
$$
if the minimum exists.
(This is Lemma 1 in Fast recognition of rings and lattices by Goralcik, Goralcikova, Koubek, and Rodl.)

This suggests the following algorithm for finding whether any two elements have a join (we can similarly determine whether any two elements have a meet):


Arrange the elements in decreasing topological order $x_1,\ldots,x_n$.
For $i=1,\ldots,n$, attempt to compute $x_j \lor x_i$ for all $j &lt; i$.
Return TRUE if all attempts were successful.


In order to compute $x_j \lor x_i$, we use the following algorithm:


Let $u_1,\ldots,u_m$ be the elements covering $x_i$.
Set $a \gets x_j \lor u_1$.
For $i=2,\ldots,m$, check whether $x_j \lor u_i \leq a$ (i.e., if $(x_j \lor u_i) \lor a = a$), and if so, set $a \gets x_j \lor u_i$.
Verify that $a \leq x_j \lor u_i$ (i.e., that $a \lor (x_j \lor u_i) = x_j \lor u_i$) for all $i=1,\ldots,m$.
If verification was successful, return $a$.


Finding a topological ordering takes time $O(n+|E|)$.
If we denote by $C(x)$ the number of elements covering $x$, then the rest of the algorithm runs in time proportional to $\sum_{i=1}^n iC(x_i) \leq n|E|$, since $\sum_i C(x_i) = |E|$. In total, we get a running time of $O(n|E|)$.

It is known that the covering relation of a semilattice contains $O(n^{3/2})$ edges (see Statement 3 in the paper mentioned above). Hence we can abort the algorithm if $|E|$ is larger, and otherwise we can assume that $|E| = O(n^{3/2})$, and so the algorithm above runs in time $O(n^{5/2})$. This is Theorem 2 in the paper mentioned above.

Concluding, we can determine whether a DAG is the covering relation of a lattice in time $O(n^{5/2})$. A recent survey by Freese, Algorithms for finite, finitely presented and free lattices mentions obtaining faster algorithms as an open problem (Problem 1 in the survey).