Space-time tradeoffs in negative cycle detection - An empirical analysis of the Stressing Algorithm

This paper discusses space-time tradeoffs associated with algorithms for the problem of detecting negative cost cycles in networks (NCCD). NCCD is one of the more ubiquitous problems in computer science and operations research, with applications ranging from program verification and real-time scheduling to image segmentation and shortest path identification. Typical algorithmic analysis, whether theoretical or empirical, focuses almost exclusively on the running time of the algorithm. However, there exist applications in which space is just as important a parameter as time is. This is especially true when the problem instances are very large, as is the case in program verification. Consequently, an algorithm that minimizes running time while ignoring the space overhead may be impractical. In this paper, we analyze a number of the more common algorithms for NCCD from the perspectives of both time and space, with a view towards providing a space-time tradeoff for the practitioner. All the algorithms discussed in this paper (with the exception of Network Simplex) run in O (m · n) time on a network with m arcs and n vertices; however, their space requirements range from O (1) (Stressing Algorithm) to Ω (n) (all the Bellman-Ford and Network Simplex variants). Our empirical results demonstrate that in the cases where space is paramount, the Stressing Algorithm is a useful alternative to the Bellman-Ford variants.