# Can the shortest simple cycle between two given nodes be found in polynomial time?

Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, the problem is NP-complete if the two constraint were changed to arbitrary, but what if the number is given?

The problem isn't NP-hard, one way to solve it is to treat the graph as a flow network where each edge has capacity $1$ and cost $1$, and set $s$ as the source and $t$ as the sink, if you find a minimum-cost flow of $2$, you have two edge-disjoint paths from $s$ to $t$ (just finding a flow of 2 or more gives disjoint paths - this is basically Menger's Theorem - the min-cost part will lead to shortest cycles).

Of course what we really want is vertex disjoint paths, rather than edge disjoint. If we treat the input graph $G$ as a digraph $D$, replacing each edge $uv$ with two edges $(u,v)$ and $(v,u)$, we can create a new graph $D'$ by splitting each vertex $v$ into $v_{1}$ and $v_{2}$ with the edge $(v_{1},v_{2})$ with cost zero, and any edge $(u,w)$ in $D$ becomes $(u_{2},w_{1})$ in $D'$. Then edges disjoint paths in $D'$ correspond to vertex disjoint paths in $D$ (and hence $G$).

Now we only need to solve the min-cost part. Suurballe & Tarjan (Networks 14(2), pp. 325–336, 1984) give an algorithm to do this with running time $O(m\log_{1+m/n}n)$ where $m$ is number of edges and $n$ the number of vertices, which is somwhere between $O(n^{2})$ and $O(n\log n)$, depending on how dense the graph is.

This may not be the fastest though: Bjorklund, Husfeldt & Taslaman (published at SODA '12, the linked version is a preprint) give a randomised FPT algorithm for finding the shortest cycle that includes a set of $k$ specified vertices, but in the introduction they also mention a (deterministic) linear time algorithm for $k=3$, which suggests $k=2$ should be quicker than the older algorithms suggest too.

What is NP-hard is finding long cycles (the extreme case is Hamiltonian Cycle).

• can you explain a bit more why would flows yield shortest paths? – 0xfff0 Jul 10 '13 at 7:02
• It should be minimum-cost flow. Add constraints that each edge has cost equals 1, and you want to find a flow of 2 with minimum cost. – Chao Xu Jul 10 '13 at 21:32
• @michael.z yes, as Chao Xu says, it should be minimum-cost flow. I'll put a nicer version in the answer, but the quick version is that a min-cost flow of 2 will give you two edge disjoint paths, and you reduce the vertex disjoint paths problem to the edge disjoint version. – Luke Mathieson Jul 11 '13 at 0:23