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!



Finding a vertex equidistant from two given vertices in a digraph
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](http://en.wikipedia.org/wiki/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).


