TR06-156 Authors: Tomas Feder, Rajeev Motwani

Publication: 15th December 2006 18:32

Downloads: 2876

Keywords:

We show how to find in Hamiltonian graphs a cycle of length

$n^{\Omega(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^3)$ time a cycle in $G$ of length

$k^{\Omega(1/\log d)}$. From this we infer that if $G$ has a cycle

of length $k$, then one can find in $O(n^3)$ time a cycle of

length $k^{\Omega(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~\cite{g} showing that if $G$ has

a cycle of length $k$, then one can find in polynomial time a cycle in

$G$ of length $\exp(\Omega(\sqrt{\log k/\log \log k}))$.

%The results presented here improve the bound of Gabow when

%$d\leq\exp(o(\sqrt{\log k\log\log k}))$ or

%$k\geq n/\exp(o(\sqrt{\log n\log\log n}))$.

We finally show that if $G$ has fixed Euler genus $g$ and has a cycle with $k$

vertices (or a 3-cyclable minor $H$ with $k$ vertices), then we can find in

polynomial time a cycle in $G$ of length $f(g)k^{\Omega(1)}$, running

in time $O(n^2)$ for planar graphs.