Finding large cycles in Hamiltonian graphs

ABSTRACT

We show how to find in Hamiltonian graphs a cycle of length n^{Ω(1/log log n)}. This is a consequence of a more general result in which we show that if G has maximum degree d and has a cycle with k vertices (or a 3-cyclable minor H with k vertices), then we can find in O(n³) time a cycle in G of length k^{Ω(1/log d)}. From this we infer that if G has a cycle of length k, then one can find in O(n³) time a cycle of length k^{Ω(1/(log(n/k)+log log n))}, which implies the result for Hamiltonian graphs. Our results improve, for some values of k and d, a recent result of Gabow [8] showing that if G has a cycle of length k, then one can find in polynomial time a cycle in G of length exp(Ω(√log k/log log k)).

REFERENCES

• 1: Cristina Bazgan , Miklos Santha , Zsolt Tuza, On the approximation of finding a(nother) hamiltonian cycle in cubic hamiltonian graphs, Journal of Algorithms, v.31 n.1, p.249-268, April 1999 [doi>10.1006/jagm.1998.0998]
• 2: Andreas Björklund , Thore Husfeldt, Finding a Path of Superlogarithmic Length, SIAM Journal on Computing, v.32 n.6, p.1395-1402, 2003 [doi>10.1137/S0097539702416761]
• 3: A. Björklund, T. Husfeldt, and S. Khanna. "Approximating longest directed path." ECCC Report Number 32, 2003. To appear in ICALP (2004).
• 4: G. Chen, J. Xu, and X. Yu. "Circumference of graphs with bounded degree." Manuscript (2004).
• 5: Tomás Feder , Rajeev Motwani , Carlos Subi, Approximating the Longest Cycle Problem in Sparse Graphs, SIAM Journal on Computing, v.31 n.5, p.1596-1607, 2002 [doi>10.1137/S0097539701395486]
• 6: T. Feder, R. Motwani, and A. Zhu. "k-connected spanning subgraphs of low degree." Manuscript (2004).
• 7: Martin Fürer , Balaji Raghavachari, Approximating the minimum degree spanning tree to within one from the optimal degree, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.317-324, September 1992, Orlando, Florida, United States
• 8: Harold N. Gabow, Finding paths and cycles of superpolylogarithmic length, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007418]
• 9: J. E. Hopcroft and R. E. Tarjan. "Dividing a graph into triconnected components," SIAM Journal on Computing 2--3 (1973), pp. 135--158.
• 10: Bill Jackson, Longest cycles in 3-connected cubic graphs, Journal of Combinatorial Theory Series B, v.41 n.1, p.17-26, Aug. 1986 [doi>10.1016/0095-8956(86)90024-9]
• 11: B. Jackson and N. C. Wormald. "Longest cycles in 3-connected graphs of bounded maximum degree." In: Graphs, Matrices, and Designs, R. S. Rees (editor), Marcle and Dekker (1993), pp. 237--254.
• 12: D. Karger, R. Motwani, and G. D. S. Ramkumar. "On approximating the longest path in a graph." Algorithmica 18 (1997), pp. 82--98.
• 13: A. S. LaPaugh and R. L. Rivest. "The subgraph homeomorphism problem." Journal of Computer and System Sciences 20 (1980), pp. 133--149.
• 14: R. Ravi , Balaji Raghavachari , Philip N. Klein, Approximation Through Local Optimality: Designing Networks with Small Degree, Proceedings of the 12th Conference on Foundations of Software Technology and Theoretical Computer Science, p.279-290, December 18-20, 1992
• 15: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]