how to find shortest simple cycles in directed graph that contain two given nodes

Question

*this problem can be NP-hard

I am looking for algorithm to find shortest simple cycle (every node in cycle is traversed exactly once) in directed (unweighted for simplicity) graph that contain two given nodes, also it would be nice to have polynomial time instead bruteforce-like solutions (although some NP solutions with good optimizations may be valuable)

one idea is to use Dijkstra and in second step "inverted" Dijkstra although, after normal Dijkstra removing traversed arcs/edges may disconnect graph which should contain cycle for given nodes,

any ideas would be welcome

Answer 1

Input: A digraph $G=(V,E)$ and two vertices $u,v \in V$.

Output: The shortest simple directed cycle in $G$ containing $u$ and $v$.

I am not sure if we could use a 2-disjoint shortest path approach for the directed case as well (a version in which we find a shortest path from $u$ to $v$ and one from $v$ to $u$ and these paths are disjoint). This problem seems to be $\mathcal{NP}$-hard in general for directed graphs, but I am not sure. There might be a neat solution.

However, we could use Johnson's algorithm. It numbers the vertices from $1$ to $|V|$ and finds all cycles containing the smallest numbered vertex, and continues with the next one and so on. So we modify it such that our vertex $u$ receives the smallest number and we only iterate over the cycles containing $u$. While doing so, we keep track of the lengths of each such cycle and if a cycle contains $v$ we temporarily store it to some variable $C$. In each iteration we compare the length of each new match (that is a cycle containing $u$ and $v$) with the length of $C$ and if it is smaller, we replace the value of $C$ with the new cycle. We do that for each cycle. Then return $C$.

Johnson's algorithm is implemented in NetworkX and you could fork their implementation from here. Johnson's algorithm is implemented in the method "simple_cycles(G)".

Input: An undirected graph $G=(V,E)$ and two vertices $u,v \in V$.

Output: The shortest simple cycle in $G$ containing $u$ and $v$.

This works for undirected graphs. We translate the undirected graph into its directed version (replace each undirected each by two directed edges being inverse to each other) and use Suurballe‘s algorithm exploiting the fact that the union of two shortest disjoint paths with the same endpoints form a shortest cycle in an undirected graph. It finds two edge disjoint shortest paths between two vertices $u$ and $v$ by running Dijsktra‘s algorithm twice.

There is a nice running example in this article.

Notice that standard Suurballe is not necessarily vertex disjoint but we can modify it as described in both provided articles:

The version of Suurballe's algorithm as described above finds paths that have disjoint edges, but that may share vertices. It is possible to use the same algorithm to find vertex-disjoint paths, by replacing each vertex by a pair of adjacent vertices, one with all of the incoming adjacencies u-in of the original vertex, and one with all of the outgoing adjacencies u-out.