The longest path problem has a polynomial solution on interval graphs (Q639287)

It is well-known that the problem of finding a longest path in a general graph is NP-hard. The authors of this article describe a polynomial algorithm for finding a longest path in an interval graph. Their algorithm uses a dynamic programming approach and runs in \(O(n^4)\) where \(n\) is the number of vertices of the graph. This paper settles an open problem posed in [\textit{R. Uehara} and \textit{Y. Uno}, ``Efficient algorithms for the longest path problem,'' Lect. Notes Comput. Sci. 3341, 871--883 (2004; Zbl 1116.05318)].