patternMinor
Can the shortest simple cycle between two given nodes be found in polynomial time?
Viewed 0 times
cyclecansimplethenodesshortestpolynomialtimetwobetween
Problem
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?
Solution
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).
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).
Context
StackExchange Computer Science Q#13194, answer score: 5
Revisions (0)
No revisions yet.