ON APPROXIMATING THE LONGEST PATH IN A GRAPH

We consider the problem of approximating the longest path in undirecte d graphs. In an attempt to pin down the best achievable performance ra tio of an approximation algorithm for this problem, we present both po sitive and negative results. First, a simple greedy algorithm is shown to find long paths in dense graphs. We then consider the problem of f inding paths in graphs that are guaranteed to have extremely long path s. We devise an algorithm that finds paths of a logarithmic length in Hamiltonian graphs. This algorithm works for a much larger class of gr aphs (weakly Hamiltonian), where the result is the best possible. Sinc e the hard case appears to be that of sparse graphs, we also consider sparse random graphs. Here we show that a relatively long path can be obtained, thereby partially answering an open problem of Broder er al. To explain the difficulty of obtaining better approximations, we also prove hardness results. We show that, for any epsilon < 1, the proble m of finding a path of length n - n(epsilon) in an n-vertex Hamiltonia n graph is NP-hard. We then show that no polynomial-time algorithm can find a constant factor approximation to the longest-path problem unle ss P = NP. We conjecture that the result can be strengthened to say th at, for some constant delta > 0, finding an approximation of ratio n(d elta) is also NP-hard. As evidence toward this conjecture, we show tha t ii any polynomial-time algorithm can approximate the longest path to a ratio of 2(O(logl-epsilon n)), for any epsilon > 0, then NP has a q uasi-polynomial deterministic time simulation. The hardness results ap ply even to the special case where the input consists of bounded degre e graphs.