## February 17, 2017:

#
An $O(nm)$ time algorithm for finding the min length directed cycle in a graph

##
Juan José Besa Vial

We introduce an $O(nm)$ time algorithm to determine the minimum
length directed cycle in a directed network with $n$ nodes and $m$
arcs and with no negative length directed cycles. This result improves
upon the previous best time bound of $O(nm + n^2 \log\log n)$. Our
algorithm first determines the cycle with minimum mean length
$\lambda^*$ in $O(nm)$ time. Subsequently, it chooses node potentials
so that all reduced costs are $\lambda^*$ or greater. It then solves
the all pairs shortest path problem, but restricts attention to paths
of length at most $n\lambda^*$. We speed up the shortest path
calculations to $O(m)$ per source node, leading to an $O(nm)$ running
time in total. We also carry out computational experiments comparing
the performance of the proposed methods and other state-of-the-art
methods. Experiments confirmed that it is advantageous to solve the
minimum mean cycle problem prior to solving shortest path
problems. Analysis of our experiments suggest that the running time to
solve the minimum length directed cycle problem was much faster than
$O(n^2)$ on average.

(Based on a paper from SODA 2017 by James Orlin and Antonio Sedeño-Noda.)