Form the product graph $\Gamma \times \Gamma$ whose vertices are pairs $(u, u') \in \Gamma \times \Gamma$ and paths edges $(p, p') : (u, u') \to (v, v')$ are pairs of paths 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).
|
3 | edited body | ||
|
|
||||
|
|
2 | added 180 characters in body; added 33 characters in body; edited body; added 75 characters in body | ||
|
Form the product graph $\Gamma \times \Gamma$ whose vertices are pairs $(u, u') \in \Gamma \times \Gamma$ and paths $(p, p') : (u, u') \to (v, v')$ are pairs of paths $p : u \to v$, $p' : u' \to v'$. Let $\Delta = \lbrace (u, u) \mid u \in V(\Gamma) \rbrace$ be the diagonal. The Your question is then equivalent to the question whether $\Delta$ can be reached from a given vertex $(x,y)$ in the graph $\Gamma \times \Gamma$. 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 . 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$).\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). |
||||
|
|
1 |
|
||
|
Form the product graph $\Gamma \times \Gamma$ whose vertices are pairs $(u, u') \in \Gamma \times \Gamma$ and paths $(p, p') : (u, u') \to (v, v')$ are pairs of paths $p : u \to v$, $p' : u' \to v'$. Let $\Delta = \lbrace (u, u) \mid u \in V(\Gamma) \rbrace$ be the diagonal. The question is then whether $\Delta$ can be reached from a given vertex $(x,y)$ in $\Gamma \times \Gamma$. 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$). |
||||
