Finding a long directed cycle

ABSTRACT

For fixed k we present linear and almost-linear time algorithms to find a directed cycle of length ≥ k, if one exists. We find a directed cycle of length ≥ log n/log log n in polynomial time, if one exists. Under an appropriate complexity assumption it is known to be impossible to improve this by more than a log log n factor. Our approach is based on depth-first search.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Noga Alon , Raphael Yuster , Uri Zwick, Color-coding, Journal of the ACM (JACM), v.42 n.4, p.844-856, July 1995 [doi>10.1145/210332.210337]
• 3: N. Alon, R. Yuster and U. Zwick, Finding and counting given length cycles, Algorithmica, 17 (1997), pp. 209--223.
• 4: Hans L. Bodlaender, On linear time minor tests with depth-first search, Journal of Algorithms, v.14 n.1, p.1-23, Jan. 1993 [doi>10.1006/jagm.1993.1001]
• 5: Andreas Björklund , Thore Husfeldt, Finding a Path of Superlogarithmic Length, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.985-992, July 08-13, 2002
• 6: A. Björklund, T. Husfeldt and S. Khanna, Approximating longest directed path, Electronic Colloq. on Comp. Complexity, Rept. No. 32, 2003.
• 7: Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
• 8: M. R. Fellows , M. A. Langston, On search decision and the efficiency of polynomial-time algorithms, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.501-512, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73055]
• 9: Russel Impagliazzo , Ramamohan Paturi, On the complexity of K-SAT, Journal of Computer and System Sciences, v.62 n.2, p.367-375, March 2001 [doi>10.1006/jcss.2000.1727]
• 10: B. Monien, How to find long paths efficiently, Annals Disc. Math., 25 (1985), pp. 239--254.
• 11: R.E. Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput., 1 (1972), pp. 146--160.
• 12: R. Tarjan, Finding dominators in directed graphs, SIAM J. Comput., 3 (1974), pp. 62--89.
• 13: Raphael Yuster , Uri Zwick, Finding Even Cycles Even Faster, SIAM Journal on Discrete Mathematics, v.10 n.2, p.209-222, May 1997 [doi>10.1137/S0895480194274133]