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]-&gt;[1]-&gt;[2]-&gt;[B] from A to B, and one [B]-&gt;[3]-&gt;[4]-&gt;[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]-&gt;[x]-&gt;[y]-&gt;[z]-&gt;[B] and [B]-&gt;[z]-&gt;[y]-&gt;[x]-&gt;[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 &quot;copied&quot; 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 &quot;copied&quot; 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.