On the Performance of a Simple Approximation Algorithm for the Longest Path Problem - Phuong, Nguyen Thi; Duc, Tran Vinh; Thanh, Le Cong (Journal of Computer Science and Cybernetics, 2019)
The longest path problem is known to be NP-hard. Moreover, they cannot be approximated within a constant ratio, unless P=NP. The best known polynomial time approximation algorithms for this problem essentially find a path of length that is the logarithm of the optimum. In this paper we investigate the performance of an approximation algorithm for this problem in almost every case. We show that a simple algorithm, based on depth-first search, finds on almost every undirected graph G=(V,E) a path of length more than |V|-3|V| |V| and so has performance ratio less than 1+4|V|/|V|.