1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think I see what you mean. I will try to work it out on a piece of paper... Thanks $\endgroup$ Nov 28, 2020 at 17:32

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.