3
$\begingroup$

Given a multi-undirected graph, how can I find the number of different paths from Node A to B using every node in the graph (means shortest path algorithms are useless)

In some cases there may be no way to achieve this. I am looking for the number of available different paths.

Note: You have to use every node and use them once.

  • 1
    This is surely NP-Hard. Hamiltonian Path can easily be reduced to it.2010-12-15

1 Answers 1

3

This problem is #P-complete. Informally, that essentially means that the best you can do is try every possible path.

See https://cstheory.stackexchange.com/questions/2396/counting-the-number-of-hamiltonian-cycles-in-cubic-hamiltonian-graphs for a more complete discussion of this problem.