Circular path visiting fewest nodes
I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good solution.
Given a directed graph, and nodes A and B, I want to find a route that takes me from A to B and back to A again, going through the fewest number of nodes. I have attempted to solve it with various versions of the shortest path problem, but it doesn't get me there. There could be a short path [A]->[1]->[2]->[B] from A to B, and one [B]->[3]->[4]->[A], that I can stitch together to get a tour that visits four nodes besides A an B (the nodes 1, 2, 3, and 4). But there might also be longer paths, [A]->[x]->[y]->[z]->[B] and [B]->[z]->[y]->[x]->[A] that ends up only visiting three nodes, because the paths overlap.
If I try to use a standard shortest-path approach, my thinking was to conceptually double the graph, so edges out of B would go into a copy of the graph, and look for the shortest path from A to A' where A' is the copy of node A. 835
That gives me a shortest path cycle, but if I visit the same node going from B to A as I do going from A to B, then it counts as much as visiting a new node, where it should be free. The cost of visiting a node in the "copied" graph depends on the path I took in the first graph, and if I start carrying that information with me, the heap I use for finding the shortest path has to remember not only a node but a path. The state-space explodes, and so does the running time.
I am not convinced that this is something that has an efficient solution, and I might be able to brute-force something with a branch-and-bound approach that does track paths, changing the scoring of nodes in the "copied" graph. But before I start thinking along that path (no pun intended), I would like to know that I am not missing something trivial and that the problem has an efficient solution.
I would greatly appreciate any pointers to how to attack this problem, or just confirmation that it might be a problem that doesn't have an efficient solution, so I can give up on trying to find one. 835