AIB 2009-11: The Longest Path Problem is Polynomial on Interval Graphs
Carsten Fuhs
http://aib.informatik.rwth-aachen.de:
The Longest Path Problem is Polynomial on Interval Graphs
Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos
AIB 2009-11
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.