Stressing is Better Than Relaxing for Negative Cost Cycle Detection in Networks

摘要

This paper is concerned with the problem of checking whether a network with positive and negative costs on its arcs contains a negative cost cycle. We introduce a fundamentally new approach for negative cost cycle detection; our approach, which we term as the Stressing Algorithm, is based on exploiting the connections between the Negative Cost Cyle Detection (NCCD) problem and the problem of checking whether a system of difference constraints is feasible. The Stressing Algorithm is an incremental, comparison-based procedure which is asymptotically optimal, modulo the fastest comparison-based algorithm for this problem. In particular, on a network with n vertices and m edges, the Stressing Algorithm takes O(m· n) time to detect the presence of a negative cost cycle or to report that none exist. A very important feature of the Stressing Algorithm is that it uses zero extra space; this is in marked contrast to all known algorithms that require Ω(n) extra space.