6
$\begingroup$

Suppose I have a directed simple graph $\Gamma$ (no edge loops or multi-edges) and a directed path $v_0v_1\cdots v_k$ joining vertex $s=v_0$ to vertex $t=v_k$. By directed path I mean that each pair $v_{i-1}v_i$ is a directed edge. Now suppose that for some $i$, the pair $v_{i-1}v_{i+1}$ is an edge, then we can omit vertex $v_i$ and still have a directed path joining $s$ and $t$.

One can think of these two paths as two routes around a triangle. Using the language of algebraic topology I would say that the two paths are homotopic. (Actually the term homotopic would mean the equivalence relation generated by such changes of path). One can then talk about homotopy classes of paths joining $s$ and $t$.

1) Does this have a name in graph theory?

and

2) Is there a theory which provides an algorithm to find the shortest path (in a weighted directed graph) in a given homotopy class?

So for question 2) one may be given a path and asked to find the shortest equivalent path. Dijkstra's algorithm applied directly wont help as it finds the shortest of all paths. It's possible Question 2) may have been considered only for graphs with no directed cycles.

$\endgroup$
  • $\begingroup$ Could you clarify on what is your criterion for two paths to be homotopic? It's a bit hazy for me. $\endgroup$ – Dániel G. Mar 30 '15 at 17:02
  • $\begingroup$ Sure. Say that two paths differ by a triangle if one can change an adjacent pair of edges uv,vw in one path to an edge uw to obtain the other path. Then two paths are homotopic if there is a sequence of paths, each differing from the previous one by a triangle. $\endgroup$ – James Griffin Mar 30 '15 at 17:20
  • $\begingroup$ @JamesGriffin It can be seen that the problem directed Hamiltonian $s$-$t$-path can be polynomially reduced to your second question, hence we cannot have a polynomial algorithm unless $P=NP$. I have also thought about how we should define such equivalence classes, should we choose "walk" instead of "path" as in algebraic topology? $\endgroup$ – Salomo Apr 1 '15 at 19:13
  • $\begingroup$ @Salomo I don't see directly how the Hamiltonian problem relates to question 2) above, however I would not be surprised by your conclusion. I suspect the problem is as hard as finding the fundamental group(or category) of the directed graph and then solving the word problem in that group (category). $\endgroup$ – James Griffin Apr 3 '15 at 10:52
  • $\begingroup$ @Salomo With respect to your second point, in algebraic topology there's really not much distinction between walks and paths. The reason we usually work with walks is that they can be concatenated to give a group structure, but most results still hold for paths. $\endgroup$ – James Griffin Apr 3 '15 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.