Shiksha Nation
Skip to content

Longest path problem

Problem of finding the longest simple path for a given graph

  • 7 min read
  • 5 chapters

Related on Lably

Through Graph (discrete mathematics)

NP-hardness

The NP-hardness of the unweighted longest path problem can be shown using a reduction from the Hamiltonian path problem: a graph G has a Hamiltonian path if and only if its longest path has length n − 1, where n is the number of vertices in G. Because the Hamiltonian path problem is NP-complete, this reduction shows that the decision version of the longest path problem is also NP-complete. In this decision problem, the input is a graph G and a number k; the desired output is yes if G contains a path of k or more edges, and no otherwise.

If the longest path problem could be solved in polynomial time, it could be used to solve this decision problem, by finding a longest path and then comparing its length to the number k. Therefore, the longest path problem is NP-hard. The question "does there exist a simple path in a given graph with at least k edges" is NP-complete.

In weighted complete graphs with non-negative edge weights, the weighted longest path problem is the same as the Travelling salesman path problem, because the longest path always includes all vertices.

Sign up free to read the rest

4 more chapters are free with a Lably account.

Already have an account?

More in From Lably lessons