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

Consider a directed cycle from $$A$$ to $$B$$ and back with the minimum number of nodes, and subject to that, with the minimum number of edges. The directed cycle is composed of two paths: $$A\to B$$ and $$B\to A$$. Since the cycle minimizes the number of edges, these paths are simple. However, it may be that the two paths are not disjoint. If so, let $$x$$ be the first node on $$B\to A$$ which appears in $$A\to B$$. This decomposes the cycle as follows: $$A\to x \to B \to x \to A.$$ By construction, the cycle $$x \to B \to x$$ is simple (no nodes are repeated). Also, the condition on the number of edges guarantees that all nodes on this cycle do not appear in $$A\to x$$ or $$x \to A$$ (otherwise, we could take shortcuts that would shorten the cycle). Therefore, if we denote the optimal cost of an $$A\to B\to A$$ cycle by $$c(A,B)$$ (excluding the two endpoints) and the optimal cost of a simple $$A\to B\to A$$ cycle by $$s(A,B)$$, we have $$c(A,B) = \min(s(A,B), \min_x c(A,x) + s(x,B) + 1).$$ We can compute $$c(A,B)$$ iteratively: start with $$c(A,B) = s(A,B)$$ (which you know how to compute), and then repeatedly apply the equation above until the situation stabilizes, which should happen within $$n$$ iterations or so.