2008 | OriginalPaper | Chapter
Finding Long Paths, Cycles and Circuits
Authors : Harold N. Gabow, Shuxin Nie
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We present a polynomial-time algorithm to find a cycle of length
$\exp(\Omega(\sqrt{\log \ell}))$
in an undirected graph having a cycle of length ≥ ℓ. This is a slight improvement over previously known bounds. In addition the algorithm is more general, since it can similarly approximate the longest circuit, as well as the longest
S
-circuit (i.e., for
S
an arbitrary subset of vertices, a circuit that can visit each vertex in
S
at most once). We also show that any algorithm for approximating the longest cycle can approximate the longest circuit, with a square root reduction in length. For digraphs, we show that the long cycle and long circuit problems have the same approximation ratio up to a constant factor. We also give an algorithm to find a
vw
-path of length ≥ log
n
/loglog
n
if one exists; this is within a loglog
n
factor of a hardness result.