Longest path problem


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 and the decision version of the problem, which asks whether a path exists of at least some given length, is NP-complete. This means that the decision problem 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.



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.[2]


Acyclic graphsEdit


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, 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.


  1. Find a topological ordering of the given DAG.


This is equivalent to running the shortest-path algorithm on −G.

Critical pathsEdit




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".[6] The best polynomial time approximation algorithm known for this case achieves only a very weak approximation ratio,  .[7] 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.[8]

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  .[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  .[9]

Parameterized complexityEdit


  1. Perform a depth-first search of the graph. Let   be the depth of the resulting depth-first search tree.
  3. Apply dynamic programming 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.[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.


Special classes of graphsEdit

A linear-time algorithm for finding a longest path in a tree was proposed by Dijkstra in 1960's, while a formal proof of this algorithm was published in 2002.[15] Furthermore, a longest path can be computed in polynomial time on weighted trees, on block graphs, on cacti,[16] on bipartite permutation graphs,[17] and on Ptolemaic graphs.[18]

For the class of interval graphs, an  -time algorithm is known, which uses a dynamic programming approach.[19] This dynamic programming approach has been exploited to obtain polynomial-time algorithms on the greater classes of circular-arc graphs[20] and of co-comparability graphs (i.e. of the complements of comparability graphs, which also contain permutation graphs),[21] both having the same running time  . 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.[23]

Furthermore, the longest path problem is solvable in polynomial time on any class of graphs with bounded treewidth or bounded clique-width, such as the distance-hereditary graphs. Finally, it is clearly NP-hard on all graph classes on which the Hamiltonian path problem is NP-hard, such as on split graphs, circle graphs, and planar graphs.

A simple model of a directed acyclic graph is the Price model, developed by Derek J. de Solla Price to represent citation networks. This is simple enough to allow for analytic results to be found for some properties. For instance, the length of the longest path, from the n-th node added to the network to the first node in the network, scales as[24]  .

See alsoEdit


  1. ^ Schrijver, Alexander (2003), Combinatorial Optimization: Polyhedra and Efficiency, Volume 1, Algorithms and Combinatorics, vol. 24, Springer, p. 114, ISBN 9783540443896.
  6. ^ a b Björklund, Andreas; Husfeldt, Thore; Khanna, Sanjeev (2004), "Approximating longest directed paths and cycles", Proc. Int. Coll. Automata, Languages and Programming (ICALP 2004), Lecture Notes in Computer Science, vol. 3142, Berlin: Springer-Verlag, pp. 222–233, MR 2160935.
  7. ^ Gabow, Harold N.; Nie, Shuxin (2008), "Finding long paths, cycles and circuits", International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 5369, Berlin: Springer, pp. 752–763, doi:10.1007/978-3-540-92182-0_66, ISBN 978-3-540-92181-3, MR 2539968. For earlier work with even weaker approximation bounds, see Gabow, Harold N. (2007), "Finding paths and cycles of superpolylogarithmic length" (PDF), SIAM Journal on Computing, 36 (6): 1648–1671, doi:10.1137/S0097539704445366, MR 2299418 and Björklund, Andreas; Husfeldt, Thore (2003), "Finding a path of superlogarithmic length", SIAM Journal on Computing, 32 (6): 1395–1402, doi:10.1137/S0097539702416761, MR 2034242.
  8. ^ Karger, David; Motwani, Rajeev; Ramkumar, G. D. S. (1997), "On approximating the longest path in a graph", Algorithmica, 18 (1): 82–98, doi:10.1007/BF02523689, MR 1432030, S2CID 3241830.
  9. ^ a b Alon, Noga; Yuster, Raphael; Zwick, Uri (1995), "Color-coding", Journal of the ACM, 42 (4): 844–856, doi:10.1145/210332.210337, MR 1411787, S2CID 208936467.
  10. ^ Bodlaender, Hans L. (1993), "On linear time minor tests with depth-first search", Journal of Algorithms, 14 (1): 1–23, doi:10.1006/jagm.1993.1001, MR 1199244. For an earlier FPT algorithm with slightly better dependence on the path length, but worse dependence on the size of the graph, see Monien, B. (1985), "How to find long paths efficiently", Analysis and design of algorithms for combinatorial problems (Udine, 1982), North-Holland Math. Stud., vol. 109, Amsterdam: North-Holland, pp. 239–254, doi:10.1016/S0304-0208(08)73110-4, ISBN 9780444876997, MR 0808004.
  11. ^ Chen, Jianer; Lu, Songjian; Sze, Sing-Hoi; Zhang, Fenghui (2007), "Improved algorithms for path, matching, and packing problems", Proc. 18th ACM-SIAM Symposium on Discrete algorithms (SODA '07) (PDF), pp. 298–307.
  12. ^ Koutis, Ioannis (2008), "Faster algebraic algorithms for path and packing problems", International Colloquium on Automata, Languages and Programming (PDF), Lecture Notes in Computer Science, vol. 5125, Berlin: Springer, pp. 575–586, CiteSeerX, doi:10.1007/978-3-540-70575-8_47, ISBN 978-3-540-70574-1, MR 2500302, archived from the original (PDF) on 2017-08-09, retrieved 2013-08-09.
  13. ^ Williams, Ryan (2009), "Finding paths of length k in O*(2k) time", Information Processing Letters, 109 (6): 315–318, arXiv:0807.3026, doi:10.1016/j.ipl.2008.11.004, MR 2493730, S2CID 10295448.
  14. ^ Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket (2009), "Clique-width: on the price of generality", Proc. 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09) (PDF), pp. 825–834, archived from the original (PDF) on 2012-10-18, retrieved 2012-12-01.
  15. ^ Bulterman, R.W.; van der Sommen, F.W.; Zwaan, G.; Verhoeff, T.; van Gasteren, A.J.M. (2002), "On computing a longest path in a tree", Information Processing Letters, 81 (2): 93–96, doi:10.1016/S0020-0190(01)00198-3.
  16. ^ Uehara, Ryuhei; Uno, Yushi (2004), "Efficient algorithms for the longest path problem", Isaac 2004, Lecture Notes in Computer Science, 3341: 871–883, doi:10.1007/978-3-540-30551-4_74, ISBN 978-3-540-24131-7.
  17. ^ Uehara, Ryuhei; Valiente, Gabriel (2007), "Linear structure of bipartite permutation graphs and the longest path problem", Information Processing Letters, 103 (2): 71–77, CiteSeerX, doi:10.1016/j.ipl.2007.02.010.
  18. ^ Takahara, Yoshihiro; Teramoto, Sachio; Uehara, Ryuhei (2008), "Longest path problems on Ptolemaic graphs", IEICE Transactions, 91-D (2): 170–177, doi:10.1093/ietisy/e91-d.2.170.
  19. ^ Ioannidou, Kyriaki; Mertzios, George B.; Nikolopoulos, Stavros D. (2011), "The longest path problem has a polynomial solution on interval graphs", Algorithmica, 61 (2): 320–341, CiteSeerX, doi:10.1007/s00453-010-9411-3, S2CID 7577817.
  20. ^ Mertzios, George B.; Bezakova, Ivona (2014), "Computing and counting longest paths on circular-arc graphs in polynomial time", Discrete Applied Mathematics, 164 (2): 383–399, CiteSeerX, doi:10.1016/j.dam.2012.08.024.
  21. ^ Mertzios, George B.; Corneil, Derek G. (2012), "A simple polynomial algorithm for the longest path problem on cocomparability graphs", SIAM Journal on Discrete Mathematics, 26 (3): 940–963, arXiv:1004.4560, doi:10.1137/100793529, S2CID 4645245.
  22. ^ Corneil, Derek G.; Krueger, Richard (2008), "A unified view of graph searching", SIAM Journal on Discrete Mathematics, 22 (4): 1259–1276, doi:10.1137/050623498.
  23. ^ Ioannidou, Kyriaki; Nikolopoulos, Stavros D. (2011), "The longest path problem is polynomial on cocomparability graphs" (PDF), Algorithmica, 65: 177–205, CiteSeerX, doi:10.1007/s00453-011-9583-5, S2CID 7271040.
  24. ^ Evans, T.S.; Calmon, L.; Vasiliauskaite, V. (2020), "The Longest Path in the Price Model", Scientific Reports, 10 (1): 10503, arXiv:1903.03667, Bibcode:2020NatSR..1010503E, doi:10.1038/s41598-020-67421-8, PMC 7324613, PMID 32601403

External linksEdit