Lowest common ancestor similar algorithm for a graph
If the lowest common ancestor of two types always exists and is unique, then your structure is a join-semilattice. Computing the lowest common ancestor is possible, but the worst case runtime complexity is not as good as I would have expected intuitively. I asked a related question some time ago, but was too lazy to write an answer after I found the relevant solution in the &quot;literature&quot;. I just wrote the answer now, and it starts as follows:

This blogpost on lattice theory has a useful reference section, which contains among others &quot;Lattice Theory with Applications&quot; by Vijay K. Garg.
Chapter 2 &quot;Representing Posets&quot; describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

Here is the relevant part from chapter 2.3.1:

We now give an $O(n + |e_\prec|)$ algorithm to compute the join of two elements $x$ and $y$. The algorithm returns $null$ if the join does not exist. We first assume that we are using the cover relation. To compute $join(x,y)$, we proceed as follows:

Step 0: Color all nodes white.
Step 1: Color all nodes reachable from $x$ as grey. This can be done by a BFS or a DFS starting from node $x$.
Step 2: Do a BFS/DFS from node $y$. Color all grey nodes reached as black.
Step 3: We now determine for each black node $z$, the number of black nodes that point to $z$. Call this number $inBlack[z]$ for any node $z$. This step can be performed in $O(n + |e_\prec|)$ by going through the adjacency lists of all black nodes and maintaining cumulative counts for $inBlack$ array.
Step 4: We count the number of black nodes $z$ with $inBlack[z]$ equal to $0$. If there is exactly one node, we return that node as the answer. Otherwise, we return $null$.