Longest Path Problem - 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 .

Read more about this topic:  Longest Path Problem

Other articles related to "approximation":

Cellular Approximation
... In algebraic topology, in the cellular approximation theorem, a map between CW-complexes can always be taken to be of a specific type ... The content of the cellular approximation theorem is then that any continuous map f X → Y between CW-complexes X and Y is homotopic to a cellular map, and if f is already cellular on a subcomplex A of X ...
Common Integrals In Quantum Field Theory - Integrals That Can Be Approximated By The Method of Stationary Phase
... of small the integral can be evaluated in the stationary phase approximation ... In this approximation the integral is over the path in which the action is a minimum ... Therefore, this approximation recovers the classical limit of mechanics ...
Sparse Approximation
... Sparse approximation (also referred to as sparse decomposition) is the problem of estimating a sparse multi-dimensional vector, satisfying a linear system of equations given high-dimensional observed data and a design ... Sparse approximation techniques have found wide use in applications such as image processing, audio processing, biology, and document analysis ...
Model Solid Approximation
... The model solid approximation is a method used for determining the extrema of energy bands in semiconductors ... fluctuates on an atomic scale, the model solid approximation averages these fluctuations out to obtain a constant energy level for each material ...