ECCC-Report TR06-156https://eccc.weizmann.ac.il/report/2006/156Comments and Revisions published for TR06-156en-usFri, 15 Dec 2006 18:32:09 +0200
Paper TR06-156
| Finding large cycles in Hamiltonian graphs |
Tomas Feder,
Rajeev Motwani
https://eccc.weizmann.ac.il/report/2006/156We 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.
Fri, 15 Dec 2006 18:32:09 +0200https://eccc.weizmann.ac.il/report/2006/156