Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
Must the paths be simple? Suppose $\gamma$ includes a cycle of length $k$. Then one could repeat the cycle and lengthen the path by $k, 2k, 3k, \ldots$ while still reaching the same vertices. –  Joseph O'Rourke Feb 5 '13 at 1:50
    
Joseph, the paths don't need to be simple unfortunately. –  Vidit Nanda Feb 5 '13 at 1:53
    
What are the graphs like ? If there are directed cycles A,B,C of lengths 6,10,15 (or any list of cycles whose combined lengths have gcd 1) which can be visited in that order from both x and y then yes. If $A$ is the adjacency matrix then you could compute $A^2$,$A^4$ etc. If there is a z with non zero value in both the xz and yz positions in any one of these (for example if one has all entries positive then again yes. Is that path counting? –  Aaron Meyerowitz Feb 5 '13 at 3:58
    
Aaron's suggestion makes me think that there is a reduction from the Frobenius coin problem to this one. However, the reduction I am thinking of is exponential; it may be that doing a reduction in the other direction will yield a polynomial time solution (to borrow Aaron's example, polynomial in 6, 10 and 15 and not polynomial in their logs). I don't see such a reduction being more clever than Aaron's adjacency matrix suggestion. Gerhard "Reduce, Recycle, And Reuse Mathematics" Paseman, 2013.02.04 –  Gerhard Paseman Feb 5 '13 at 5:27
add comment

2 Answers 2

up vote 5 down vote accepted

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).

share|improve this answer
    
Probably you meant to write "edge" or "arc" instead of "path" the first two times. Nice solution. –  Brendan McKay Feb 5 '13 at 11:35
    
Thanks, fixed "paths" to "edges". –  Andrej Bauer Feb 5 '13 at 11:41
    
This is absolutely fantastic. Thanks a ton! –  Vidit Nanda Feb 5 '13 at 13:50
add comment

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$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.