From: Andreas =?iso-8859-1?Q?Bj=F6rklund?= <Andreas.Bjorklund@cs.lth.se>
Subject: Re: Biggest cycle, undirected graph.
Date: Fri, 25 Aug 2000 17:29:41 +0200
Newsgroups: sci.math
Summary: [missing]

Loic Taloc wrote:
> 
> Hi,
> I have the following problem, I'd like to find the biggest cycle in an
> undirected graph.
> 
> Thanks
> Loic
And so would the rest of the computational complexity world, but it
appears to be an extremely hard problem. The best result is perhaps due
to Zwick et al, stating that given a graph on n vertices containing a
path of length O(log n), a path of length O(log n) can be found in
polynomial time. If you know the graph is hamiltonian, a result by
Viswanathan states that a path of length O(log^2 n/log^2 log n) can be
found in polynomial time. Obviously, finding cycles is it least as hard.
My advice to you is to try to characterize the graphs for which you want
to find long cycles, and try some heuristics.
Regards,
Andreas