I am given a directed acyclic graph (DAG) with a unique source and sink. Is there an efficient way to test whether the partial order represented by this graph is a lattice?In other words, I need to test whether any two vertices have a unique least upper bound and greatest lower bound.From brief browsing, I found an $O(n^3)$ algorithm that explicitly computes the least upper bound of every pair of elements. Is there a better test?
Testing if a given DAG is a lattice
graphs;lattices;order theory