The Longest Path Problem is Polynomial on Interval Graphs
Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos
The longest path problem is the problem of finding a path of maximum
length in a graph. Polynomial solutions for this problem are known only
for small classes of graphs, while it is NP-hard on general graphs, as
it is a generalization of the Hamiltonian path problem. Motivated by
the work of Uehara and Uno in~\cite{Ueh04}, where they left the longest
path problem open for the class of interval graphs, in this paper we show
that the problem can be solved in polynomial time on interval graphs. The
proposed algorithm runs in $O(n^4)$ time, where $n$ is the number of
vertices of the input graph, and bases on a dynamic programming approach.