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. In contrast to the shortest path problem, which can be solved in polynomial time in graphs without negative-weight cycles, the longest path problem is NP-hard, meaning that it cannot be solved in polynomial time for arbitrary graphs unless P = NP. Stronger hardness results are also known showing that it is difficult to approximate. However, it has a linear time solution for directed acyclic graphs, which has important applications in finding the critical path in scheduling problems.
Read more about Longest Path Problem: NP-hardness, Acyclic Graphs and Critical Paths, Approximation, Parameterized Complexity, Special Classes of Graphs, See Also
Famous quotes containing the words longest, path and/or problem:
“A bill... is the most extraordinary locomotive engine that the genius of man ever produced. It would keep on running during the longest lifetime, without ever once stopping of its own accord.”
—Charles Dickens (1812–1870)
“They take abuse
with smiles,
their hardship
with great ceremony,
their quarrels
with tears:
This is the path of good women.”
—Hla Stavhana (c. 50 A.D.)
“The general public is easy. You don’t have to answer to anyone; and as long as you follow the rules of your profession, you needn’t worry about the consequences. But the problem with the powerful and rich is that when they are sick, they really want their doctors to cure them.”
—Molière [Jean Baptiste Poquelin] (1622–1673)