关键词: 最长路径，k- Path问题，NP难，参数计算

Abstract: The longest path problem is well-known NP-Hard, and has significant applications in many fields such as bioinformatics. After the emerging of parameterized computation theory, the parameterized k-Path problem becomes one of the most concerned research problems. We introduced several algorithms to solve the longest path problem, including approximate algorithms,parameterized algorithms and polynomial time algorithms on special graphs. We put emphasis on the analysis and comparison of the latest results in parameterized algorithm, which use color-coding, divide-and-conquer and algebra techniques to solve k-Path problem. At last, we presented some further research directions for this problem.

Key words: Longest path, k-Path problem, NP-hard, Parameterized computation