Longest Path Problem - Approximation

Approximation

Bjorklund, Husfeldt & Khanna (2004) write that the longest path problem in unweighted undirected graphs "is notorious for the difficulty of understanding its approximation hardness". The best polynomial time approximation algorithm known for this case achieves only a very weak approximation ratio, . For all, it is not possible to approximate the longest path to within a factor of unless NP is contained within quasi-polynomial deterministic time; however, there is a big gap between this inapproximability result and the known approximation algorithms for this problem.

In the case of unweighted but directed graphs, strong inapproximability results are known. For every the problem cannot be approximated to within a factor of unless P=NP, and with stronger complexity-theoretic assumptions it cannot be approximated to within a factor of . The color-coding technique can be used to find paths of logarithmic length, if they exist, but this gives an approximation ratio of only .