Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs

ABSTRACT

This paper is concerned with the problem of recognizing, in a graph with rational vector-weights associated 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 dynamic graphs and to the validity of some systems of recursive formulas. It was previously conjectured that combinatorial algorithms exist for the cases of two- and three-dimensional vector-weights. The present paper gives strongly polynomial algorithms for any fixed dimension. Moreover, these algorithms also establish membership in the class NC. On the other hand, it is shown that when the dimension of the weights is not fixed, the problem is equivalent to the general linear programming problem under strongly polynomial and logspace reductions.

REFERENCES

• 1: K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
• 2: L. Danzer, B. Griinbaum and V. Klee, "Helly's theorem and its relatives, :' in: Proc. Syrup Pu,'e Math. 7, American Mathematical Society, 1963, pp. 101-180.
• 3: M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
• 4: B. Grfinbaum, Convez polytopes, Interscience-~r~riley, London, 1967.
• 5: K. Iwano , K. Steiglitz, Testing for cycles in infinite graphs with periodic structure, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.46-55, January 1987, New York, New York, United States [doi>10.1145/28395.28401]
• 6: R. M. Karp, "A characterization of' the minimum cycle mean in a digraph," Discrete Maihematics 23 (1978) 309-311.
• 7: Richard M. Karp , Raymond E. Miller , Shmuel Winograd, The Organization of Computations for Uniform Recurrence Equations, Journal of the ACM (JACM), v.14 n.3, p.563-590, July 1967 [doi>10.1145/321406.321418]
• 8: S. Rao Kosaraju , Gregory Sullivan, Detecting cycles in dynamic graphs in polynomial time, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.398-406, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62251]
• 9: N. Megiddo, "Combixtatori~d optimization with rational objective functions," Matkematics of Oper, ztior~s Research 4 (1979) 414-424.
• 10: N. Megiddo, "Applying parMlel computation algorithms in the design of serml algorithms," J. 2tssoc. Comput. Mach. 30 (1983) 337-341.
• 11: N. Megiddo, "Towards a genuinely polynomial algorithm for linear programming," SIAM Journal on Computir~g 12 (1983)347-353.
• 12: Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
• 13: J. B. Orlin, "Some problems in dynamic/periodic graphs," in: Progress in in Combinatorial Optimization, W. R. Pullyblank, E;d., Academic Press, Orlando, Florida, 1984, pp. 273-293.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

General Terms:
Algorithms, Theory