Planar Negative k -Cycle

Given an edge-weighted directed graph G, the N egative - k -C ycle problem asks whether G contains a negative-weight cycle with at most k edges. For k = 3 the problem is known as the N egative T riangle 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 N egative -k-C ycle problem can be solved in min{O( nk 2 log n ), O ( n 2 )} time. Assuming the min-plus convolution conjecture, we then show, for k > n 1/3 that there is no algorithm polynomially faster than, 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.

Authors

• Pawel Gawrychowski
• Shay Mozes
• Oren Weimann

Keywords

No keywords are indexed for this paper.