Finding a vertex equidistant from two given vertices in a digraph

Question

The question is essentially in the title: while attempting to compute the colimit of a diagram of cell complexes, my colleague and I find ourselves stumped with the following graph theoretic problem:

Given a directed (unweighted) graph $\Gamma$ and vertices $x,y$, does there exist a vertex $z$ along with directed paths $\gamma:x \to z$ and $\eta:y \to z$ so that the lengths of $\gamma$ and $\eta$ are equal?

The annoying aspect is that these paths need not be the shortest paths connecting $x$ or $y$ to $z$, so everything I can think of (or easily find in a textbook) goes out of the window. For instance, the usual Dijkstra's algorithm and breadth-first search type approaches don't (I think!) yield anything useful when applied naively.

My question is

Does there exist an efficient algorithm to solve this equidistant vertex problem? If not, is there any algorithm which performs better than the dumb path-enumeration?

Thanks for your help!

Answer 1

Form the product graph $\Gamma \times \Gamma$ whose vertices are pairs $(u, u') \in \Gamma \times \Gamma$ and edges $(p, p') : (u, u') \to (v, v')$ are pairs of edges $p : u \to v$, $p' : u' \to v'$. Let $\Delta = \lbrace (u, u) \mid u \in V(\Gamma) \rbrace$ be the diagonal. Your question is equivalent to the question whether $\Delta$ can be reached from a given vertex $(x,y)$ in the graph $\Gamma \times \Gamma$ (and finding such a vertex, but most algorithms automatically give you one). This does not seem to be that hard to solve as it is just a reachability problem. If you want it in classical form, attach every vertex in $\Delta$ to a special vertex $\infty$ and ask for a path from $(x,y)$ to $\infty$. There are algorithms which preprocess the graphs so that subsequent reachability queries can be answered fast, in case you have to do this a lot (Wikipedia explains some of this).

Answer 2

The set of walk lengths between two given vertices is a regular language, so it is the union of a finite number of (finite or infinite) arithmetic progressions. It is routine to determine whether two arithmetic progressions have an element in common, so the question comes down to how quickly this representation of the set of lengths can be computed. Unfortunately I think the number of arithmetic progressions might in general be exponential in the size of the graph.

Another problem it reduces to is whether two rational functions in a single variable have a power in common. (I mean a power of the variable that has nonzero coefficient in the Taylor expansion about 0.) The degrees of the numerators and denominators are at most $n$.