The longest path
Kent Quanrud · 73:17 · Watch on YouTube
The longest simple path is solvable in linear time on a directed acyclic graph by memoized recursion, but the Hamiltonian-path decision problem is NP-hard on general directed graphs and, by a local vertex gadget, on u...