Finding a Path of Superlogarithmic Length
Andreas Björklund, Thore Husfeldt · SIAM Journal on Computing · 2003
We consider the problem of finding a long, simple path in an undirected graph. We present a polynomial-time algorithm that finds a path of length $\Omega\bigl((\log L/\log\log L)^2\bigr)$, where L denotes the length of the longest simple path in the graph. This establishes the performance ratio O(n(log log n/log n) 2 ) for the longest path problem, where n denotes the number of vertices in the graph.