Longest Path

The longest path problem asks to find a path of maximum length in a given graph. The problem is NP-complete, but there exists an efficient dynamic programming solution for acyclic digraphs.

The detour matrix is a real symmetric matrix whose th entry is the length of the longest path from vertex to vertex .

For a traceable graph, longest paths correspond to Hamiltonian paths.

Finding a longest path is challenging for stacked book graphs and Apollonian networks.