Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR06-156 | 7th December 2006 00:00

Finding large cycles in Hamiltonian graphs

TR06-156
Authors: Tomas Feder, Rajeev Motwani
Publication: 15th December 2006 18:32
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint