Longest path problem
Encyclopedia
In the mathematical
discipline of graph theory
, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices. Unlike the shortest path problem
, which asks for the shortest path between two vertices and can be solved in polynomial time in graphs without negative-weight cycles, the decision version of this problem is NP-complete
, which means that the optimal solution cannot be found in polynomial time unless P = NP.
The standard decision version of this problem asks whether the graph contains a simple path of length greater than or equal to k, where the length of a path is defined to be the number of edges
along the path.
. Clearly, if a certain general graph has a Hamiltonian path, this Hamiltonian path is the longest path possible, as it traverses all possible vertices. To solve the Hamiltonian path problem using an algorithm for the longest path problem, we use the algorithm for the longest path problem on the same input graph and set k=|V|-1, where |V| is the number of vertices in the graph.
If there is a Hamiltonian path in the graph, then the algorithm will return yes, since the Hamiltonian path has length equal to |V|-1. Conversely, if the algorithm outputs yes, there is a simple path of length |V|-1 in the graph. Since it is a simple path of length |V|-1, it is a path that visits all the vertices of the graph without repetition, and this is a Hamiltonian path by definition.
Since the Hamiltonian path problem is NP-complete, this reduction shows that this problem is NP-hard
. To show that it is NP-complete, we also have to show that it is in NP. This is easy to see, however, since the certificate
for the yes-instance is a description of the path of length k.
, the longest path problem on G can be solved in linear time using dynamic programming
. Assume that topOrder(G) outputs a sequence of vertices in topological order (This can be computed via a topological sort and this step requires that the input graph is a directed acyclic graph). Furthermore, let V(G) be the set of vertices of G and E(G) be the set of edges in G and, if weights are defined, let weight (G, e) be the weight of an edge e in the graph G (if the graph is unweighted, insert an arbitrary constant other than zero for any occurrence of weight (G,e)). Then the following algorithm computes the length of the longest path:
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
Correctness can be checked as follows: The topological order traverses the given graph in layers of ascending distance from the source vertices of the graph (at first, all vertex with distance 0 from the source vertices, then all vertices with distance 1 from the source vertices, ...). For each vertex, it clearly holds that a path of maximum length consists of a path of maximum distance through all the layers which are closer to the source than this vertex and also an edge of maximum length connecting the longest path up to this node with this node. This is exactly length_to(w) = max(weight(G, (v, w)) + length_to(v)) for all edges (v,w) in G, just written in prose. Considering that the topological order traverses all possible vertices v on the previous layer before traversing w shows that the implementation computes exactly this maximum for each vertex and thus, the maximum of all lengths to a vertex is the correct length.
The worst-case running time of this algorithm is O(T + |V| + |E| + |V|), if T is the time required by the topological order. Assuming a standard algorithm for computing the topological order, this simplifies into O(|V| + |E| + |V| + |E| + |V|), which simplifies further into O(|V| + |E|).
Furthermore, extending this algorithm to compute the actual path is straightforward. In order to do this, it is necessary to introduce a predecessor (or successor)-array which is updated whenever the length_to is modified. Given this, one can try to reconstruct the path from the sources and sinks of the directed acyclic graph and once there is a path of maximum length reconstructed, this is one of the longest paths.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
discipline of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the longest path problem is the problem of finding a simple path of maximum length in a given graph. A path is called simple if it does not have any repeated vertices. Unlike the shortest path problem
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized...
, which asks for the shortest path between two vertices and can be solved in polynomial time in graphs without negative-weight cycles, the decision version of this problem is NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
, which means that the optimal solution cannot be found in polynomial time unless P = NP.
The standard decision version of this problem asks whether the graph contains a simple path of length greater than or equal to k, where the length of a path is defined to be the number of edges
Edge (geometry)
In geometry, an edge is a one-dimensional line segment joining two adjacent zero-dimensional vertices in a polygon. Thus applied, an edge is a connector for a one-dimensional line segment and two zero-dimensional objects....
along the path.
NP-completeness
The NP-completeness of the decision problem can be shown using a reduction from the Hamiltonian path problemHamiltonian path problem
In the mathematical field of graph theory the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph . Both problems are NP-complete...
. Clearly, if a certain general graph has a Hamiltonian path, this Hamiltonian path is the longest path possible, as it traverses all possible vertices. To solve the Hamiltonian path problem using an algorithm for the longest path problem, we use the algorithm for the longest path problem on the same input graph and set k=|V|-1, where |V| is the number of vertices in the graph.
If there is a Hamiltonian path in the graph, then the algorithm will return yes, since the Hamiltonian path has length equal to |V|-1. Conversely, if the algorithm outputs yes, there is a simple path of length |V|-1 in the graph. Since it is a simple path of length |V|-1, it is a path that visits all the vertices of the graph without repetition, and this is a Hamiltonian path by definition.
Since the Hamiltonian path problem is NP-complete, this reduction shows that this problem is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
. To show that it is NP-complete, we also have to show that it is in NP. This is easy to see, however, since the certificate
Certificate (complexity)
In computational complexity theory, a certificate is a string that certifies the answer to a computation, or certifies the membership of some string in a language...
for the yes-instance is a description of the path of length k.
Relation to the shortest path problem
The longest path problem can be reduced to the shortest path problem (although the graph may have negative-weight cycles), by exploiting the duality of optimizations (maximizing a positive value is the same as minimizing a negative value). If the input graph to the longest path problem is G, the shortest simple path on the graph H, which is exactly the same as G but with edge weights negated, is the longest simple path on G. However, any positive-weight cycles in the original graph G lead to negative-weight cycles in H. Finding the shortest simple path on a graph with negative-weight cycles is therefore also NP-complete. If G contains no cycles, then H will have no negative-weight cycles, and any shortest-path finding algorithm can now be run on H to solve the original problem in polynomial time. Thus the longest path problem is easy on acyclic graphs.Algorithms for acyclic graphs
As mentioned above, the longest path problem on acyclic graphs can be solved in polynomial time by negating the edge weights and running a shortest-path finding algorithm. The algorithm described below does not use this reduction and achieves a better time complexity.Weighted directed acyclic graphs
If G is a directed acyclic graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
, the longest path problem on G can be solved in linear time using dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
. Assume that topOrder(G) outputs a sequence of vertices in topological order (This can be computed via a topological sort and this step requires that the input graph is a directed acyclic graph). Furthermore, let V(G) be the set of vertices of G and E(G) be the set of edges in G and, if weights are defined, let weight (G, e) be the weight of an edge e in the graph G (if the graph is unweighted, insert an arbitrary constant other than zero for any occurrence of weight (G,e)). Then the following algorithm computes the length of the longest path:
algorithm dag-longest-path is
input:
Directed acyclic graph G
output:
Length of the longest path
length_to = array with |V(G)| elements of type int with default value 0
for each vertex v in topOrder(G) do
for each edge (v, w) in E(G) do
if length_to[w] <= length_to[v] + weight(G,(v,w)) then
length_to[w] = length_to[v] + weight(G, (v,w))
return max(length_to[v] for v in V(G))
Correctness can be checked as follows: The topological order traverses the given graph in layers of ascending distance from the source vertices of the graph (at first, all vertex with distance 0 from the source vertices, then all vertices with distance 1 from the source vertices, ...). For each vertex, it clearly holds that a path of maximum length consists of a path of maximum distance through all the layers which are closer to the source than this vertex and also an edge of maximum length connecting the longest path up to this node with this node. This is exactly length_to(w) = max(weight(G, (v, w)) + length_to(v)) for all edges (v,w) in G, just written in prose. Considering that the topological order traverses all possible vertices v on the previous layer before traversing w shows that the implementation computes exactly this maximum for each vertex and thus, the maximum of all lengths to a vertex is the correct length.
The worst-case running time of this algorithm is O(T + |V| + |E| + |V|), if T is the time required by the topological order. Assuming a standard algorithm for computing the topological order, this simplifies into O(|V| + |E| + |V| + |E| + |V|), which simplifies further into O(|V| + |E|).
Furthermore, extending this algorithm to compute the actual path is straightforward. In order to do this, it is necessary to introduce a predecessor (or successor)-array which is updated whenever the length_to is modified. Given this, one can try to reconstruct the path from the sources and sinks of the directed acyclic graph and once there is a path of maximum length reconstructed, this is one of the longest paths.
External links
- NP-Completeness
- Source of the algorithm
- "Find the Longest Path", song by Dan BarrettDaniel J. BarrettDaniel J. Barrett is a writer, software engineer, and musician. He is best known for his technology books, his work with progressive rock band Gentle Giant, and the imaginary computer game BLAZEMONGER.-Writing:...