An approximation algorithm for computing longest paths

We show how the color-coding method by Alon, Yuster and Zwick, in its version specialized to compute simple paths of a specified cardinality k, can be extended to address the presence of arc lengths (the existence of such an extension was outlined by the authors for a more general color-coding algorithm, but it was not explicitely described, and its time complexity was not discussed). The extension is then used to derive approximation results for the general longest path problem.