  We study the design of fixed-parameter algorithms for problems already known
to be solvable in polynomial time. The main motivation is to get more efficient
algorithms for problems with unattractive polynomial running times. Here, we
focus on a fundamental graph problem: Longest Path, that is, given an
undirected graph, find a maximum-length path in $G$. Longest Path is NP-hard in
general but known to be solvable in $O(n^{4})$ time on $n$-vertex interval
graphs. We show how to solve Longest Path on Interval Graphs, parameterized by
vertex deletion number $k$ to proper interval graphs, in $O(k^{9}n)$ time.
Notably, Longest Path is trivially solvable in linear time on proper interval
graphs, and the parameter value $k$ can be approximated up to a factor of 4 in
linear time. From a more general perspective, we believe that using
parameterized complexity analysis may enable a refined understanding of
efficiency aspects for polynomial-time solvable problems similarly to what
classical parameterized complexity analysis does for NP-hard problems.
