| has gloss | eng: 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. |
