Menu
I'd like to add another approximation algorithm, a parametrized one: For a fixed δ>0 (or more preciesly, δ=Ω(1poly(k)) ), you can compute a (1+δ)-approximation of the number of simple paths, in either undirected or directed graph, of length k in time O∗(2O(k)).
Because there are exactly eight paths of length four from a to d. By inspecÅon of the graph, we see that a,b,a,b,d; a,b,a,c,d; a,b,d,b,d; a,b,d,c,d; a,c,a,b,d; a,c,a,c,d; a,c,d,b,d; and a, c, d, c, d are the eight paths of length four from a to d.
This type of graph traversal is called Backtracking. Backtracking for above graph can be shown like this: The red color vertex is the source vertex and the light-blue color vertex is destination, rest are either intermediate or discarded paths. This give four paths between source(A) and destination(E) vertex.
I am looking the number of unique x length paths through a graph starting at a particular node.
However I have a restriction that no node is visited more than once on any path.
For example take the following graph:
If I am after the number of 3 length paths starting at 5.
The answer would be 9.
5 -> 2 -> 1 -> 3
5 -> 2 -> 4 -> 3
5 -> 2 -> 4 -> 7
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 4 -> 7 -> 6
5 -> 6 -> 7 -> 4
5 -> 7 -> 4 -> 2
5 -> 7 -> 4 -> 3
Note I am only concerted with the answer (9) not the specific paths.
I have tried using an adjacency matrix to the power of x to give the number of paths, but I cannot work out how to account for unique node restriction.
I have also tried using a depth-first search but the amount of nodes and size of x makes this infeasible.
EDIT: Confused DFS with BFS (Thank you Nylon Smile & Nikita Rybak).
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With