Finding a vertex equidistant from two given vertices in a digraph - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T02:40:17Z http://mathoverflow.net/feeds/question/120820 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/120820/finding-a-vertex-equidistant-from-two-given-vertices-in-a-digraph Finding a vertex equidistant from two given vertices in a digraph Vidit Nanda 2013-02-05T01:39:11Z 2013-02-05T11:40:53Z <p>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:</p> <blockquote> <p>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?</p> </blockquote> <p>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.</p> <p>My question is</p> <blockquote> <p>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?</p> </blockquote> <p>Thanks for your help!</p> http://mathoverflow.net/questions/120820/finding-a-vertex-equidistant-from-two-given-vertices-in-a-digraph/120850#120850 Answer by Brendan McKay for Finding a vertex equidistant from two given vertices in a digraph Brendan McKay 2013-02-05T10:19:25Z 2013-02-05T10:19:25Z <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/120820/finding-a-vertex-equidistant-from-two-given-vertices-in-a-digraph/120851#120851 Answer by Andrej Bauer for Finding a vertex equidistant from two given vertices in a digraph Andrej Bauer 2013-02-05T10:52:14Z 2013-02-05T11:40:53Z <p>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 <a href="http://en.wikipedia.org/wiki/Reachability" rel="nofollow">reachability</a> 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).</p>