4
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ can you explain a bit more why would flows yield shortest paths? $\endgroup$ – zee Jul 10 '13 at 7:02
  • $\begingroup$ 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. $\endgroup$ – Chao Xu Jul 10 '13 at 21:32
  • $\begingroup$ @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. $\endgroup$ – Luke Mathieson Jul 11 '13 at 0:23

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.