Longest path

from Wikipedia, the free encyclopedia
By removing any red edge, a simple path of maximum length is obtained from this Hamiltonian circle.

The task of finding the simple path of maximum length in a given graph is referred to in graph theory and theoretical computer science as the longest path problem . A path is called simple if it does not contain any node more than once . The length of the path can be measured in two ways: either by the number of edges or (in a weighted graph ) by the sum of the weights of its edges.

In contrast to the problem of the shortest path , which can be solved in polynomial running time , the problem of the longest path belongs to the group of NP-hard problems. This means that it cannot be solved in polynomial running time, unless P = NP . It can be shown that an approximation is also difficult. However, for directed , non-cyclic graphs, the problem can be solved using a topological sort in linear time. An important field of application is finding the critical path in planning tasks.

NP severity

The NP severity of the problem of the unweighted longest path can be shown with the help of the Hamilton path problem . A graph has a Hamilton path only if its longest path is length , where the number of nodes is in. Since the Hamilton path problem is NP-complete, the decision version of the longest path problem is also NP-complete . In the decision version, the input consists of the graph and a number . The output is "yes" if it contains a simple path with or more edges.

If the longest path problem could be solved in polynomial running time, it could be used to solve the decision version by comparing the length of the longest path with . Hence the longest path problem is NP-hard. The question "Is there a path with at least k edges in a given graph " is NP-complete.

In a weighted full graph , the weighted longest path problem is equivalent to the traveling salesman problem , since the longest path necessarily includes all nodes.

Individual evidence

  1. Noltemeier, Hartmut: Graph Theoretical Concepts and Algorithms . 3. Edition. Vieweg + Teubner Verlag, Wiesbaden 2012, ISBN 978-3-8348-1849-2 , pp. 191 f .
  2. Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency, Volume 1 . tape 24 . Springer, 2003, ISBN 3-540-44389-4 , pp. 114 .
  3. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein (Eds.): Introduction To Algorithms . 2nd Edition. MIT Press, 2003, ISBN 0-262-03293-7 , pp. 978 .
  4. ^ Eugene Lawler: Combinatorial Optimization: Networks and Matroids . Courier Dover Publications, 2001, ISBN 0-486-41453-1 , pp. 64 .

Web links