Fix an unweighted, weakly connected digraph $ \Gamma$ , possibly with loops, and of bounded degree.

Call $ p$ a common $ n$ -ancestor of $ q_0,q_1$ if there are $ n$ -paths (directed paths of length exactly $ n$ ) from $ p$ to each $ q_i$ , and a last common ancestor if intuitively there are no common ancestors in between, i.e. for every common $ k$ -ancestor $ p’ \ne p$ of $ q_0,q_1$ , the shortest path from $ p$ to $ p’$ has length $ > n-k$ .

It is not hard to see that last common ancestors must be somewhat constrained: for example, if $ p$ is a last common ancestor of $ q_0$ and $ q_1$ then every pair of shortest $ n$ -paths from $ p$ to the respective $ q_i$ must be disjoint; what’s more, any path leading between two such respective $ n$ -paths must be of at least a certain length, depending on which points it connects between.

The question then is: how much further, and under what circumstances, can we further constrain the possible last common ancestors of a pair of nodes $ q_i$ ? I’m particularly interested in when we can infer some smallish upper bound on $ n$ , and especially when both $ q_i$ have arcs pointing to a common target node (which may itself be one of the $ q_i$ , since loops are allowed).

Some properties which might make the problem easier, in roughly increasing order of how much I’d prefer to avoid them:

the graph

• has a loop at every node;
• is strongly connected;
• is undirected;
• has polynomial growth;
• is finite (but still “large” compared with the size of bounds I’m interested in).

Not sure how best to tag this one.