# Find every path that passes through certain edges

I'm faced with the following problem:

Given

• Directed and unweighted graph, where each edge E has two attributes

Goal

• Find every path through the 3 (or more) given edges in a specific order

Questions

• Is it NP-hard?
• Is there already an algorithm for this?
• I was thinking about placing a node in every edge and than run Dijkstra algorithm to find the shortest path from A to B and then from B to C. Although, this complicates my graph. Any other ideas? Thanks
• It's not NP-hard, but there can be exponentially many such paths, see 1, 2, 3 Jun 22, 2020 at 13:48
• Does this answer your question? Efficiently enumerating all paths from i to j of given length in a graph Jun 22, 2020 at 13:48
• Thanks for the answer. I don't think that this related question answers completely to my question because i don't understand which algorithm he used but i think that storing the paths in a linked list could be useful. My problem here is that i can't find an algorithm that allows me to find paths using only edges. I was thinking about putting an extra node in every edge and using an algorithm like Dijkstra to find all the paths using these nodes. Jun 23, 2020 at 8:59
• As long as you have a simple graph, if you are given the path in terms of vertices, you can easily construct the path in terms of edges. Suppose therefore that the path is $u \to v \to w$, then clearly the edges you traverse are $uv$ and $vw$. So any algorithm that outputs the sequence of vertices can be used to construct the sequence of edges. If you have multiple edges between vertices, then each edge correspond to a different path (unless it's the one you need to pass through). Jun 23, 2020 at 10:21
• It's not clear from your question whether the edges must be visited in the order given, or in any order. Both versions can result in a factorial (super-exponential) number of paths: Consider that, given any digraph, you can add 4 new vertices $a, b, c, d$ and the edges $ab$ and $cd$, as well as an edge from $b$ to every original vertex and and edge from every original vertex to $c$. Now asking for every path that visits $ab$ and $cd$ in that order produces every path in the original graph (which is $n! + {n \choose 1}(n-1)! + {n \choose 2}(n-2)! + \dots + 1$ paths for a complete digraph). Jun 23, 2020 at 17:52