Longest Path Problem - Parameterized Complexity

Parameterized Complexity

The longest path problem is fixed-parameter tractable when parameterized by the length of the path. For instance, it can be solved in time linear in the size of the input graph (but exponential in the length of the path), by an algorithm that performs the following steps:

1. Perform a depth-first search of the graph. Let be the depth of the resulting depth-first search tree.
2. Use the sequence of root-to-leaf paths of the depth-first search tree, in the order in which they were traversed by the search, to construct a path decomposition of the graph, with pathwidth .
3. Apply dynamic programming to this path decomposition to find a longest path in time, where is the number of vertices in the graph.

Since the output path has length at least as large as, the running time is also bounded by, where is the length of the longest path. Using color-coding, the dependence on path length can be reduced to singly exponential. A similar dynamic programming technique shows that the longest path problem is also fixed-parameter tractable when parameterized by the treewidth of the graph.

For graphs of bounded clique-width, the longest path can also be solved by a polynomial time dynamic programming algorithm. However, the exponent of the polynomial depends on the clique-width of the graph, so this algorithms is not fixed-parameter tractable. The longest path problem, parameterized by clique-width, is hard for the parameterized complexity class, showing that a fixed-parameter tractable algorithm is unlikely to exist.