In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
and
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
, the longest path problem is the problem of finding a simple
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desire p ...
of maximum length in a given
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
. A path is called ''simple'' if it does not have any repeated
vertices; the length of a path may either be measured by its number of edges, or (in
weighted graph
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
s) by the sum of the weights of its edges. In contrast to the
shortest path problem, which can be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
in graphs without negative-weight cycles, the longest path problem is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
and the decision version of the problem, which asks whether a path exists of at least some given length, is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
. This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless
P = NP
The P versus NP problem is a major unsolved problem in theoretical computer science. In informal terms, it asks whether every problem whose solution can be quickly verified can also be quickly solved.
The informal term ''quickly'', used abov ...
. Stronger hardness results are also known showing that it is difficult to
approximate
An approximation is anything that is intentionally similar but not exactly equal to something else.
Etymology and usage
The word ''approximation'' is derived from Latin ''approximatus'', from ''proximus'' meaning ''very near'' and the prefix ' ...
. However, it has a
linear time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
solution for
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
s, which has important applications in finding the
critical path in scheduling problems.
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 graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is c ...
s 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.
Acyclic graphs
A longest path between two given vertices ''s'' and ''t'' in a weighted graph ''G'' is the same thing as a shortest path in a graph −''G'' derived from ''G'' by changing every weight to its negation. Therefore, if shortest paths can be found in −''G'', then longest paths can also be found in ''G''.
For most graphs, this transformation is not useful because it creates cycles of negative length in −''G''. But if ''G'' is a
directed acyclic graph
In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...
(DAG), then no negative cycles can be created, and a longest path in ''G'' can be found in
linear time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
by applying a linear time algorithm for shortest paths in −''G'', which is also a directed acyclic graph.
[.] For a DAG, the longest path from a source vertex to all other vertices can be obtained by
running the shortest-path algorithm on −''G''.
Similarly, for each vertex ''v'' in a given DAG, the length of the longest path ending at ''v'' may be obtained by the following steps:
# Find a
topological ordering
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge ''uv'' from vertex ''u'' to vertex ''v'', ''u'' comes before ''v'' in the ordering. For in ...
of the given DAG.
# For each vertex ''v'' of the DAG, in the topological ordering, compute the length of the longest path ending at ''v'' by looking at its incoming neighbors and adding one to the maximum length recorded for those neighbors. If ''v'' has no incoming neighbors, set the length of the longest path ending at ''v'' to zero. In either case, record this number so that later steps of the algorithm can access it.
Once this has been done, the longest path in the whole DAG may be obtained by starting at the vertex ''v'' with the largest recorded value, then repeatedly stepping backwards to its incoming neighbor with the largest recorded value, and reversing the sequence of vertices found in this way.
This is equivalent to running the shortest-path algorithm on −''G''.
Critical paths
The
critical path method for scheduling a set of activities involves the construction of a directed acyclic graph in which the vertices represent project milestones and the edges represent activities that must be performed after one milestone and before another; each edge is weighted by an estimate of the amount of time the corresponding activity will take to complete. In such a graph, the longest path from the first milestone to the last one is the critical path, which describes the total time for completing the project.
Longest paths of directed acyclic graphs may also be applied in
layered graph drawing
Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards.... It is also known as Sugiyama-style gra ...
: assigning each vertex ''v'' of a directed acyclic graph ''G'' to the layer whose number is the length of the longest path ending at ''v'' results in a layer assignment for ''G'' with the minimum possible number of layers.
Approximation
write that the longest path problem in unweighted undirected graphs "is notorious for the difficulty of understanding its approximation hardness".
[.]
The best polynomial time approximation algorithm known for this case achieves only a very weak approximation ratio,
. For all
, it is not possible to approximate the longest path to within a factor of
unless NP is contained within
quasi-polynomial deterministic time; however, there is a big gap between this inapproximability result and the known approximation algorithms for this problem.
In the case of unweighted but directed graphs, strong inapproximability results are known. For every
the problem cannot be approximated to within a factor of
unless P = NP, and with stronger complexity-theoretic assumptions it cannot be approximated to within a factor of
.
The
color-coding
In computer science and graph theory, the term color-coding refers to an algorithmic technique which is useful in the discovery of network motifs. For example, it can be used to detect a simple path of length in a given graph. The traditional c ...
technique can be used to find paths of logarithmic length, if they exist, but this gives an approximation ratio of only
.
[.]
Parameterized complexity
The longest path problem is
fixed-parameter tractable
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
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:
# Perform a
depth-first search
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible alon ...
of the graph. Let
be the depth of the resulting
depth-first search tree.
# 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
In graph theory, a path decomposition of a graph is, informally, a representation of as a "thickened" path graph, and the pathwidth of is a number that measures how much the path was thickened to form . More formally, a path-decomposition ...
of the graph, with pathwidth
.
# Apply
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
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
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. The gra ...
of the graph.
For graphs of bounded
clique-width
In graph theory, the clique-width of a graph is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs.
It is defined as the minimum num ...
, 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
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. T ...
class