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.

$\endgroup$
  • 1
    $\begingroup$ This is surely NP-Hard. Hamiltonian Path can easily be reduced to it. $\endgroup$ – Aryabhata Dec 15 '10 at 3:33
3
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.