Planar Negative k-Cycle

Given an edge-weighted directed graph G, the Negativek-Cycle problem asks whether G contains a negativeweight cycle with at most k edges. For k = 3 the problem is known as the NegativeTriangle problem and is equivalent to all-pairs shortest paths (and to min-plus matrix multiplication) and solvable in O(n 3 ) time. In this paper, we consider the case of directed planar graphs. We show that the Negative-k-Cycle problem can be solved in minO(nk 2 log n), O(n 2 log n) time. Assuming the minplus convolution conjecture, we then show, for k > n 1/3 that there is no algorithm polynomially faster than O(n 1.5 √ k), and for k ≤ n 1/3 that our O(nk 2 log n) upper bound is essentially tight. The latter gives the first non-trivial tight bounds for a planar graph problem in P. Our lower bounds are obtained by introducing a natural problem on matrices that generalizes both min-plus matrix multiplication and min-plus convolution, and whose complexity lies between the complexities of these two problems.