Testing if a given DAG is a lattice

Question

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.

Answer 1

I am not sure is this optimal approach, but it seems to me that it is worth a try.

Intention is to check at least as possible number of pairs of vertices for existence of meet and join. Meets and joins are checked independently with same approach. First one side (meet) than other side (join) with opposite edge orientation.

Idea is to use topological sort, and to check next visited vertex for a meet with already visited vertices. To achieve this each vertex (v) has to store:

• set of it's predecessor P(v) = {x; x < v},
• it's topological index I(v).

Finding if meet exists for two given vertices (a, b) is done by:

P_ab = P(a) intersect P(b)
Find x in P_ab with max I(x).
If |P(x)| = |P_ab| - 1 than x is a meet of a and b.

Visiting new vertex v, nodes to be checked for a meet with v are C(v) = all already visited nodes - P(v). Use property of partial order to reduce number of checks. If v and a in C(v) have a meet, and if b in C(v) and b < a, than v and b have meet (same as v and a). With that it is enough to check vertices in C(v) that have unresolved outgoing edges (U(v)). Probably it is not even needed to check all of vertices in U(v), since some of them can be ordered. To easier check vertices from U(v) in descending order by index (I(x)).

Number of checks for a meet is of order |V| * width(G), probably much smaller than |V|^2.

There is a memory issue since each vertex has to store set of it's predecessors. That is potentially |V|^2 space. That can be reduces since if visited vertex x is not in U(v) anymore only size P(x) can be checked. So, for these vertices P(x) can be deleted and |P(x)| stored instead.

Note if next visited vertex has only one in edge, than it is not needed to test it for a meet with vertices in U(v). This reasoning is even possible to extend to if su-blattice is connected by one edge to visited vertices, that all sub-lattice vertices do not have to be checked. But, it is probably quite hard to check for a sub-lattice :-)