In graph theory and theoretical computer science, 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; the length of a path may either be measured by its number of edges, or (in weighted graphs) by the sum of the weights of its edges.
This means that the decision problem cannot be solved in polynomial time for arbitrary graphs unless P = NP.
However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.
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.
The question "does there exist a simple path in a given graph with at least k edges" is NP-complete.
But if G is a directed acyclic graph (DAG), then no negative cycles can be created, and a longest path in G can be found in linear time by applying a linear time algorithm for shortest paths in −G, which is also a directed acyclic graph.
[4] 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: 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.
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.
[5] Björklund, Husfeldt & Khanna (2004) write that the longest path problem in unweighted undirected graphs "is notorious for the difficulty of understanding its approximation hardness".
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.
[8] In the case of unweighted but directed graphs, strong inapproximability results are known.
[6] The color-coding technique can be used to find paths of logarithmic length, if they exist, but this gives an approximation ratio of only
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: Since the output path has length at least as large as
[10] Using color-coding, the dependence on path length can be reduced to singly exponential.
[9][11][12][13] A similar dynamic programming technique shows that the longest path problem is also fixed-parameter tractable when parameterized by the treewidth of the graph.
For graphs of bounded clique-width, 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 latter algorithm is based on special properties of the lexicographic depth first search (LDFS) vertex ordering[22] of co-comparability graphs.
For co-comparability graphs also an alternative polynomial-time algorithm with higher running time
is known, which is based on the Hasse diagram of the partially ordered set defined by the complement of the input co-comparability graph.
A simple model of a directed acyclic graph is the Price model, developed by Derek J. de Solla Price to represent citation networks.