Planar Negative k -Cycle
Paweł Gawrychowski, Shay Mozes, Oren Weimann · Society for Industrial and Applied Mathematics eBooks · 2021
Given an edge-weighted directed graph G, the Negative-k-Cycle problem asks whether G contains a negative-weight 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(n3) time. In this paper, we consider the case of directed planar graphs. We show that the Negative-k-Cycle problem can be solved in min{O(nk2 log n), O(n2)} time. Assuming the min-plus convolution conjecture, we then show, for k > n1/3 that there is no algorithm polynomially faster than , and for k ≤ n1/3 that our O(nk2 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.