hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
Abstract:
We study the problem of finding the cycle of minimum cost-to-time ratio in a
directed graph with $ n $ nodes and $ m $ edges. This problem has a long
history in combinatorial optimization and has recently seen interesting
applications in the context of quantitative verification. We focus on strongly
polynomial algorithms to cover the use-case where the weights are relatively
large compared to the size of the graph. Our main result is an algorithm with
running time $ \tilde O (m^{3/4} n^{3/2}) $, which gives the first improvement
over Megiddo's $ \tilde O (n^3) $ algorithm [JACM'83] for sparse graphs. We
further demonstrate how to obtain both an algorithm with running time $ n^3 /
2^{\Omega{(\sqrt{\log n})}} $ on general graphs and an algorithm with running
time $ \tilde O (n) $ on constant treewidth graphs. To obtain our main result,
we develop a parallel algorithm for negative cycle detection and single-source
shortest paths that might be of independent interest.
