CODEWITHSUNDEEP
algorithmgraph
threenplusone
threenplusone

Reputation: 2122

Calculating the number of paths through graph

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:
enter image description here

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

Upvotes: 7

Views: 8488

Answers (2)

hugomg
hugomg

Reputation: 69924

This problem is a counting problem in #P (number of solutions) instead of a decision problem in NP (yes or no).

Moron's reduction still works to prove the problem is #P-Complete because Hamilton Paths is also #P-complete.

Upvotes: 3

Aryabhatta
Aryabhatta

Reputation:

This is NP-Hard.

Reduction from Hamiltonian Path.

Given a graph whose Hamiltonian Path existence we need to check...

Run your algorithm for each vertex, with a path length n-1. Any non-zero return corresponds to Hamiltonian path and vice versa.

So basically, if you find a polynomial time algorithm to solve your problem, then you have a polynomial time algorithm to solve the Hamiltonian Path problem, effectively proving P=NP!

Note: This assumes x is an input.

If you x was fixed (i.e. independent of the number of vertices in the graph), then you have O(n^x) time algorithms, which is in P, but still pretty impractical for medium sized x.

Upvotes: 10

Related Questions