# Find all sets of nodes that can be connected with a single path

** Edit: I just noticed my current algorithm is incorrect, as it only finds paths starting/ending at the given node. I'm trying to figure out a solution, but I'm a bit stuck.

Say I have an undirected graph. I would like to find all possible combinations of nodes that could be connected with a single path, that include a certain node.

--clarification: That is paths starting and ending at any node. Not just paths starting at the node in question.

Take this graph for example:

A----B
|    |
|    |
D----C


The solution for node A would be:

ABCD; example path A->B->C->D. Alternatively B->A->C->D or many others. As long as we have one, we're good.
ABC; example path C->B->A, etc.
AB
A; 'path' from itself to itself


I understand this is a -very- hard problem with a lot of results. To make it simpler it is allowed to have some duplicates in the end result, but less would be better(this makes cyclic graphs a bit easier).

My current(naive) solution is as follows:

1. Start at the node in question
2. Note current path as possible path.
3. If no possible connections, return.
4. For each possible connection, go into recursion via [2].

See the following example. The problem with my algorithm is that a lot of duplicates are generated. Here the bottom two items in the example tree are the same solution.

• From your description, it seems this algorithm must (among others) find an Hamiltonian path, if one exists in the graph. As the problem of finding such a path is NP-hard, there won't be improvements to make your algorithm efficient. However, if all you want is to reduce or completely remove the investigation of duplicate solutions, there probably is an algorithm that achieves that. Feb 13 '18 at 13:00
• Yes indeed. If I can reduce the number of duplicates(and currently make the algorithm at all, as I figured out it's incorrect), that would be great. It is part of a bigger algorithm, and duplicates make it slower. Feb 13 '18 at 13:02
• Also, I don't only need hamiltonian paths. Every node in the example tree is a valid solution. (The stated algorithm by chance works for this specific graph) Feb 13 '18 at 13:03
• If you have some nodes, and it is possible to make a path that visits those nodes exactly once(and does not touch other nodes), then that set is part of the total solution. I need to find all of those sets. Feb 13 '18 at 13:05
• Yes, you don't only need Hamiltonian paths, but since you must at least find them, this problem is NP-hard. You state this procedure is a part of a bigger algorithm. Could you perhaps say what that algorithm is or what the actual problem is you're trying to solve? It could be the case that there is a more efficient algorithm for your actual problem that doesn't use this subroutine, so this can be very relevant! Feb 13 '18 at 13:06