E. Cohen et N. Megiddo, STRONGLY POLYNOMIAL-TIME AND NC ALGORITHMS FOR DETECTING CYCLES IN PERIODIC GRAPHS, Journal of the Association for Computing Machinery, 40(4), 1993, pp. 791-830
This paper is concerned with the problem of recognizing, in a graph wi
th rational vector-weights associates with the edges, the existence of
a cycle whose total weight is the zero vector. This problem is known
to be equivalent to the problem of recognizing the existence of cycles
in periodic (dynamic) graphs and to the validity of systems of recurs
ive formulas. It was previously conjectured that combinatorial algorit
hms exist for the cases of two- and three-dimensional vector-weights.
It is shown that strongly polynomial algorithms exist for any fixed di
mension d. Moreover, these algorithms also establish membership in the
class NC. On the other hand, it is shown that when the dimension of t
he weights is not fixed, the problem is equivalent to the general line
ar programming problem under strongly polynomial and logspace reductio
ns. The algorithms presented here solve the cycle detection problem by
reducing it to instances of the parametric minimum cycle problem. In
the latter, graphs with edge-weights that are linear functions of d pa
rameters are considered. The goal, roughly, is to find an assignment o
f the parameters such that the value of the minimum weight cycle is ma
ximized. The technique we used in order to obtain strongly polynomial
algorithms for the parametric minimum cycle problem is a general tool
applicable to parametric extensions of a variety of other problems.