On contrasting vertex contraction with relaxation-based approaches for negative cost cycle detection

This paper continues the study of contrasting greedy and dynamic programming (relaxation-based) approaches for the NCCD problem, by comparing sophisticated variants of VC with sophisticated implementations of the BF algorithm. Variants of VC are obtained by employing different heuristics to determine the vertex contraction sequence, in precisely the same manner as variants of BF are obtained by employing different heuristics to determine the edge relaxation sequence. Our experiments indicate that on most classes of networks, there is at least one VC variant with a performance profile that is comparable to the more sophisticated BF implementations. Our results are most surprising for the case of planar networks, where a variant of VC performs almost as well as the best relaxation-based algorithm. One of the principal conclusions of our work is that a simple, greedy approach involving vertex contraction is a good choice on sparse networks. On a more fundamental note, we establish that the selection of an algorithm for the NCCD problem should involve an analysis of the input and the architecture of the computing machine, in order to maximize performance.